发布时间 : 星期日 文章d数据结构与算法模拟卷(1)更新完毕开始阅读2aa4e0f2f90f76c661371a77
浙江大学远程教育学院试卷
模拟考卷（1）
课程代码及名称___07040320数据结构与算法___ 考试时间：90分钟
大 题 得 分 阅卷人 一 二 三 四 五 总分 -------------------------------------------------------------------------------------
请保持卷面整洁，答题字迹工整。
一、判断题（共 20小题，每小题 1分，共 20 分，正确的打“√”，错误的打“×”。）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1. 下列算法的时间复杂性是O(n2)。 sum = 0;
for(i=n; i>=0; i--) for(j=0; j 2. 在n个元素的顺序表中删除第i个元素，需要移动n-i个元素。 3. 线性表就是每个元素都有唯一的前驱元素和唯一的后继元素。 4. 判断顺序储存下堆栈s是空的条件是s.top==0。 5. 队列中输出元素的次序总是和输入元素的次序一致。 6. 空字符串就是长度为0的字符串。 7. n(n>0)个结点的树有n-1条边。 8. 二叉树中第3层结点数至多是4个结点。 9. 若用双亲表示法存储树，则无法找到结点的所有孩子结点。 10. 满二叉树一定是完全二叉树，反之亦然。 11. 5个顶点的无向图最多可能有20条边。 12. 连通图的连通分量就是它自己。 13. 有向图各顶点入度之和就等于边的数量。 14. 不连通的图不能用深度优先遍历各个顶点。 15. 图的生成树包含了图的全部顶点。 16. 一般来说，二分查找比顺序查找快。 17. n(n>0)个结点的二叉排序树至多有log2n层。 18. 对二叉树进行中序遍历得到的序列一定有序表。 19. 二叉排序树一般用于查找某个元素。 20. 序列｛12, 23, 15, 24, 26, 14, 16, 30, 27｝是一个堆。 第1页 共6页 二、选择题（共 20 空，每空 1.5 分，共 30 分） 1. 算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是 __________ 。 A空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 2. 判定一个循环队列QU(最多元素为m)为空队列的条件是___________。 A.QU->front==QU->rear B.QU->front!=-QU->rear C.QU->front==(QU->rear+1)% m D.QU->front!=(QU->rear+1)% m 3.在一个单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行 _____ 。 A. s->next = p; p->next=s; B. s->next = p->next; p->next = s; C. s->next = p->next; p = s; D. p->next = s; s->next = p; 4. 数组A中，每个元素的长度为4个字节，行下标i从1到8，列下标j从1到10，从首地 址100开始连续存放在存储器内，存放该数组至少需要的单元素是 ____________________ 。 A. 80 B. 180 C. 320 D. 420 5. 在下列叙述中，正确的是 _____________ 。 A. 数据的逻辑结构要考虑数据元素本身的内容 B. 不同类型的数据元素可以归类到同一的逻辑结构中 C. 数据元素之间的关联关系在数据的逻辑结构中体现 D. 数据元素是数据不可分割的最小标识单位 6. 将递归算法转换成对应的非递归算法时,通常需要使用 ____________ 。 A.栈 B.队列 C链表 D树 7. 按照二叉树的定义，具有2个及2个以下结点的二叉树有_______________种。 A. 2 B. 3 C. 4 D. 5 8. 已知一有向图的邻接表存储结构如图所示 （a）根据有向图的深度优先遍历算法，从v1顶点出发，所得到的顶点序列是___________。 A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 （b）根据有向图的宽度优先遍历算法，从v1顶点出发，所得到的顶点序列是___________。 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2 10.如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序___________ 。 A. uwvts B. vwuts C. wutsv D. wuvts 11. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要___________ 条边。 A. n B. n+1 C. n/2 D. n-1 12. 串是一种特殊的线性表，其特殊性体现在 _____________。 A.只能顺序存储 B.数据元素是一个字符 第2页 共6页 C.可以链接存储 D.数据元素可以是多个字符 13. 在循环双链表的p所指结点之后插入s所指结点的操作是_________________ 。 A. p->right=s;s->left=p;p->right->left=s;s->right=p->right; B. p->right=s;p->right->left=s;s->left=p;s->right=p->right; C. s->left=p;s->right=p->right;p->right=s;p->right->left=s; D. s->left=p;s->right=p->right; p->right->left=s;p->right=s; 14. 快速排序方法在___________情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 15. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_______________。 A. 插入排序 B.选择排序 C.快速排序 D. 归并排序 16. 用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下，则采用的排序方法是_______________。 （1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 17．关于图的邻接矩阵，下列结论 _____________是正确的。 A. 有向图的邻接矩阵总是不对称的 B. 无向图的邻接矩阵总是不对称的 C. 有向图的邻接矩阵可以是对称的，也可以是不对称的 D. 无向图的邻接矩阵可以是不对称的，也可以是对称的 18. 在长度为n 的双链表中某结点（已知其地址）之前，插入一个新结点的时间复杂度是_________。 2 A. O(n) B. O(1) C. O(log2n) D. O(n) 19. 给定字符串 “this_is_a_string”，如果用一个字节存储一个字符，那么存储这个串需要_______(a)位存储空间，而用Huffman 编码，则只需要____________________(b)位存储空间。 A. 36 B. 49 C. 70 D. 128 三、填空题（共 19 空，每空 1-2 分，共 23 分） 1. 设每个元素需要4个字节，顺序存储1200个元素,若首地址是2000，那么第150个元素的地址是____________。(每空 2 分) 2. 已知两个字符串s1=”Data structure is very useful.”, s2=”uct”, 那么Strlen(s1)=___________, StrEmpty(s2)=_______, Substr(s1,9,4)=____________, Index(s1,s2,1)=________。 3. 下列表示的图中，共有_______个是树；有_______个是满二叉树；有_______个是完全二叉树。 第3页 共6页 4. 下列二叉树的中序遍历序列是______________________________________; 后序遍历序列是______________________________________。(每空 2 分) 5. 5个顶点的无向图，若要求其各个顶点的度都相同，则这种无向图有________个（不考虑顶点的差异）。( 2 分) 6. 下列有向图中，入度最大的顶点是_______；从v3到v2的最短简单路径有____________；包含所有顶点的简单路径有________________；有一简单回路是_____________。 第4页 共6页