《数据结构》试题（A卷）
（考试时间： 90分钟）
一、单项选择题（本大题共15小题，每小题2分，共30分）
（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分） 1.（ ）是组成数据的基本单位，是一个数据整体中相对独立的单元。
A．数据 B.数据元素 C.数据对象 D.数据结构
2.算法计算量的大小称为算法的（ ）。
A.效率 B.复杂度 C.数据元素之间的关系 D.数据的存储方法
3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（ ）方式最节省时间。
A.链式存储 B. 索引存储 C.顺序存储 D.散列存储 4.下述哪一条是顺序存储结构的优点？（ ）
A.存储密度大 B.插入运算方便
C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 5.在一个单链表中，若删除p所指结点的后续结点，则执行（ ）。 A.p->next=p->next->next B.p->next=p->next C.p=p->next;p->next=p->next->next D.p=p->next->next
6.带头结点的单链表head为空的判定条件是（ ）。
A.head==NULL B.head->next==NULL C.head->next==head D.head!==NULL 7.非空的循环单链表head的尾结点(由p所指向)满足（ ）。
A.p->head==NULL B.p==NULL C.p->next==head D.p==head 8.下面关于线性表的叙述中，错误的是哪一个？（ ）
A.线性表采用顺序存储，必须占用一片连续的存储单元。 B.线性表采用顺序存储，便于进行插入和删除操作。 C.线性表采用链式存储，不必占用一片连续的存储单元。 D.线性表采用链式存储，便于插入和删除操作。 9.队列操作的原则是（ ）。
A.后进先出 B.先进先出 C.只能进行插入 D.只能进行删除 10.栈中允许进行插入和删除的一端称为（ ）。
A.栈首 B.栈尾 C.栈顶 D.栈底
11．假设以数组A[n]存放循环队列的元素，其首尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．（rear-front+n）%n B. rear-front+1 C. (front-rear+n)%n D.(rear-front)%n
12.最大容量为n的循环队列，队尾指针是rear，队首指针是front，则队空的判断条件是（ ）。 A.（rear+1）%n==front B.rear==front C.rear+1==front D.(rear-1)%n==front 13. 将一个十进制的数转换成二进制的数，可以使用以下一种称为（
A. 图 B. 树 C. 广义表 D. 栈
14. 把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。
）的数据结构。
A. 有2种 B. 有3种 C. 有4种 D. 唯一的
15.一棵左右子树均不空的二叉树在先序线索化后，其中空链域的个数是（ ）。
1
A. 3 B. 2 C. 0 D. 不确定
二、填空题（本大题共10个空，每空2分，共计20分）
1．数据结构是研究程序设计中计算机操作的 以及它们之间的关系和运算的一门学科。
2．在一个单链表中，已知指针q所指结点是指针p 所指结点的前驱结点，若在q和p之间插入结点s，则应执行两条语句：___ ___ ， 。
3．字符串采用结点大小为2的链表作为其存储结构，是指链表的每个链结点的 域中只存放 了2个字符。
4．广义表（a,b,c,d）的表尾是 。
5．一棵深度为k的二叉树，最多有 个结点。 6．已知有向图G=（V，E），其中: V={v1,v2,v3,v4,v5,v6,v7},
E={
8. 图的存储常采用 和 两种方法。
三、判断题（本大题共10小题，每题1分，共10分）
（请在每小题后面的括号里写出答案，如果正确，请写“√”，如果错误，请写“×”） 1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ） 2．线性表就是顺序存储的表。（ ）
3.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。（ ）
4．线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。（ ） 5.串的长度是指串中所含不同字符的个数。（ ） 6.对稀疏矩阵进行压缩存储的目的是节省存储空间。（ ）
7.二叉树是非线性数据结构，所以它不能采用顺序存储结构存储。（ ） 8.任意一棵二叉树中至少有一个结点的度为2。（ ）
9.对线性表进行二分查找时，要求线性必须以顺序方式存储，且结点按关键字有序排序。（ ） 10.采用线性探测法解决冲突问题，所产生的一系列后继散列地址必须大于等于原散列地址。（ ）
四、应用题（本小题共5小题，每小题6分，共30分）
1.简述以下算法的功能（假设栈和队列的元素类型均为int）(6分)
void fun1(Queue &Q) {Stack S; int x;
Initstack(S);
While(!QueueEmpty(Q)) { DeQueue(Q,x); Push(S,x); } While(!StackEmpty(S)) { Pop(S,x);
2
EnQueue(Q,x);} }
2.请将如图4.1所示的一棵树转换成一棵二叉树。（6分） A
BCD EFG
图4.1 一棵树 3.给定叶结点(a,b,c,d,e,f,g)，权值分别为{23,12,15,7,17,2,8}，画出对应的哈夫曼树，并写出各叶结点的哈夫曼编码。（6分）
4.（6分）已知图G的邻接表如图4.2所示，则：
从顶点v1出发的深度优先搜索序列为____ _ __。 从顶点v1出发的广度优先搜索序列为____ _ __。
图4.2 图G的邻接表
5.求构造图4.3所示无向网的最小生成树（6分）
3