数据结构模拟试题2

1、数据结构模拟试题(二) 本试卷分两部分，第一部分为选择题，第二部分为非选择题; 分。考试时间150分钟。 选择题 20分，非选择题80分，满分100 第一部分 选择题 一、单项选择题(本大题共 20小题，每小题1分，共 在每小题列岀的四个选项中只有一个选项是符合题目要求的， 1. A. C. 2. A. C. 3. A. C. 4. A. B. C. D. 5. A. B. C. D. 6. A. B. C. D. 7. 20分) 请将正确选项前的字母填在题后的括号内。 一个存储节点存放一个【 】 数据项B.数据元素 数据结构D.数据类型 下列时间复杂度中最好的是【 0(1) O (log 2

2、n) 非空的线性表中， 开始节点 终端节点 在一个单链表中，已知 S-next=P next; P P-next=S next; S 】 B. O (n) D. O(n2) 有且只有一个直接前趋和一个直接后继的节点是【 B.内部节点 D.所有节点 Q所指节点是P所指节点的前趋节点，若在 next=S; next=P; Q next=S;S next=p; p next=S;S next=Q; 一个队列的人队序列是1, 2, 3, 4，则队列的输出序列是【】 1, 4, l , 3, 2, 3, 4, 2, 3, 2, 3, 4, 4 1 2 1 Q和P之间插入S节点【】 一个顺序栈一旦被说明，

3、其占用空间的大小【 已固定 可以改变 不能固定 动态变化 经过下列运算后，X的值是【】 (Q); EnQueue (Q, a); EnQueue(Q, a); DeQueue( Q, InitQueue a b 1 2 下列广义表是线性表的有【】 E=(a,(b,c) B . E=(a, E) E= ( a , b) D . E= (a , L) ;L=() 数组A中，每个元素A的长度为3个字节，行下标i从1到8 , X)； A. B. C. D. 8. A. C. 9. 连续存放在存储器内，该数组按行存放时，元素 A. SA+140 C. SA+ 222 10. 设 s3= ” A. ” I

4、AM” A85的地址为【 列下标j从1到10从首地址SA开始 】 B D IAM”, s4 SA+ 144 SA+ 225 =A TERCHER”， 则 strcat (s3,s4 ) B. ” I AM A TEACHER C. ” lAMA TERCHER D. ” A TERCHER 11. 完全二叉树 A.定是满 C.不是 二叉树。【 .可能是满 D. 定不是满 12在具有个接点的完全二叉树中，节点 A. 2i C. 2i + 1 13强连通分量是 A.无向图 B.不存在 D. |i/2| 的极大连通子图。 B.有向图 的父节点是【 C.树D.图 14在一个图中，所有节点的度数之和与图

5、的边数的比是【】 A.1:2B.1:2 C.2:1D.3:1 15. 若一组记录的关键码为（46, 79, 56, 38, 40, 84）,则利用快速查序的方法以第一个记录为基准得到 的一次划分结果为【】 A. 38, 40, 46, 56, 79, 84 B. 40, 38, 46, 79, 56, 84 C. 40, 38, 46, 56, 79, 84 D. 40, 38, 46, 84, 56, 79 16排序方法中，为排序序列中依次取岀元素与已排序序列（处始时为空）中的元素进行比较，将其放入 已排序序列的正确位置上方法称为【】 A.希尔排序B.冒泡排序 C.插入排序D.选择排序 17

6、顺序查找法适合于存储结构为 的线性表【 】 A.散列存储B顺序存储或链接存储 C.压缩存储D索引存储 18在查找过程中，若同时还要做增、删工作，这中查找则称为【】 A.静态查找B.动态查找 C.内查找D.外查找 19存放在外存中的数据的组织结构是【】 A.数组B .表 C.文件D.链表 20顺序文件的缺点是【】 A.不利于修改B 读取速度慢 C.只能写不能读D 写文件慢 第二部分非选择题 二、 填空题（本大题共 17小题，每空1分，共20分） 1. 一个算法的空间复杂度是指该算法所耗费的 ，它是该算法求解问题 的函数。 2链式存储方式中，指针域中只有一个指针的线性表称为 。 3在具有n个节点的

7、双链表中做插入、删除运算，平均时间复杂度为 。 4当栈空时再做退栈运算时将产生 。 5顺序队列为空的条件是 。 6. 串按存储方式可分为和。 7. 对称矩阵的下三角元素 ai,j,存放在一维数组v的元素Vk中，k与i、j的关系是：k = s=(node *)(malloc(sizeof(node); r=s;P=s1;q=s2; while (p!=null) c=(node * (malloc(size(node); c-data=p-data; r-next=c; p=p-next; r=c, new(c); c-data=q-data; rnext=c; q=q-next; r=c; r-next=null; s=s-next return(s); 2. void passbtree(bstree root) if(!