（A卷）第1页共7页
2012年韩山师范学院本科插班生考试试卷
计算机科学与技术专业数据结构试卷（A卷）
一、单项选择题（每题2分，共40分）
1、下列选项中不是算法的必须具有的重要特性的是
A.有穷性
B.正确性
C.确定性
D.可行性
。
。
2、下列关于算法渐近阶表达式中，时间复杂度最高的是
A.5n2
B.n3/2
C.2n
D.nlogn
E. n2
3、数据是对客观事物的符号表示，在计算机科学中，数据的含义广泛，如图像、声音等都属于数据范畴，数据不意义的最小不可分割的单位是
A.数据元素
。B.数据对象
C.数据结构
D.数据项
。
E.位
4、下列有关线性表的叙述中，正确的是
A.线性表中的元素必须具有相同的特性B.线性表中的元素都有且仅有一个直接前驱C.线性表中的元素都有且仅有一个直接后继D.以上表述都不正确
5、在一个长度为n有序的链式存储的线性表中插入一个元素，使其保持有序，其操作的时间复杂度是A.O(n)
B.
O(1)
C.O(
。)
D.O(n2)
。
6、关于线性表的结点的存储地址表述正确的是
A.必须是不连续的C．必须是连续的7、如下陈述中正确的是
A．串是一种特殊的线性表C．串元素中的字母不区分大小写8、数组的逻辑结构不同于下列
A.线性表
B.栈
C.树
B．连续与否由其存储方式确定D．和头结点的存储地址相连续
。
B．串的长度必须大于零D．空串与空格串是相同的概念
的逻辑结构。D.
队列
（A卷）第2页共7页
9、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为A．2n-1D．(n2+n)/2-1
B．n2
E. (n2-n)/2-1
C．(n2+n)/2F.以上都不对
。
。
10、中缀表达式(A + B) * D + E / (F + A * D) + C的后缀形式是
A.A BDEFAD C +*+ / +*+C.+*+ / +*+A BDEFADC11、链表不具有的特点是
A．插入、删除不需要移动元素C．不必事先估计存储空间
。
B．可随机访问任一元素D．所需空间与线性长度成正比
倍。
B.D *A B + E F A D * + / + C +D.A B + D * E F A D * + / + C +
12、在一个图中，所有边数等于所有顶点的度数之和的
A.1/2
B.1
C.2
D.4
13、设某棵二叉树中有2000个结点，则该二叉树的最小高度为
A.10
B.11
C.12
D.13
。
14、设某棵二叉树的中序遍历序列为BGDAECHFI，前序遍历序列为ABDGCEFHI，
则后序遍历该二叉树得到序列为A.GDBAECHFIC.GDBECHIFA
B.IHGFEDCBAD.GDBEHIFCA
。
15、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的
运算是
。
B. tail（head（head（tail（L））））
A. head（tail（tail（L）））
C. head(tail(head（tail(L））））D. head(tail(head(tail(tail（L）））))16、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为
。
A．top=top-1C.top->next=top
B.top=top->nextD.top->next=top->next
17、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为n1，
n2和n3。则与森林F对应的二叉树根结点的右子树上的结点个数
（A卷）第3页共7页
是A.n1+n2
。
B.n1+n3
C.n2+n3
D.n1+n2+n3
18、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为A.430
B.45
。C.50
D.55
条边。
D．n(n+1)/2 E．n(n-1)/2
。
19、设无向图的顶点个数为n，则该图最多有
A．n-1 B．n
C．n(n-1)
20、在二叉排序树中插入一个关键字值的平均时间复杂度为
A．O(1ogn)
B.O(n)
C.O(nlogn)
D.O(n2)。
二、名词解析（每题3分，共6分）1、平衡二叉树：
2、哈夫曼（Huffman）树：
三、填空题（每空2分，共18分）
1、在完全二叉树的第6层上最少有__________个结点，最多有_________个结点。
2、普里姆（Prime）算法的时间复杂度为______,它对______图较为适合。3、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__为
次；当使用监视哨时，若查找失败，则比较关键字的次数。
2012年韩山师范学院本科插班生《数据结构》试卷-已转换
