全国2003年10月高等教育自学考试
数据结构试题
课程代码：02331
一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题2分，共30分)
1.计算机识别、存储和加工处理的对象被统称为( )
A.数据 B.数据元素
C.数据结构 D.数据类型
2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )
A.O(1) B.O(n)
C.O(nlogn) D.O(n2)
3.队和栈的主要区别是( )
A.逻辑结构不同 B.存储结构不同
C.所包含的运算个数不同 D.限定插入和删除的位置不同
4.链栈与顺序栈相比，比较明显的优点是( )
A.插入操作更加方便 B.删除操作更加方便
C.不会出现下溢的情况 D.不会出现上溢的情况
5.采用两类不同存储结构的字符串可分别简称为( )
A.主串和子串 B.顺序串和链串
C.目标串和模式串 D.变量串和常量串
6.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是( )
A.0 B.2
C.3 D.5
7.已知广义表的表头为a，表尾为(b,c)，则此广义表为( )
A.(a,(b,c)) B.(a,b,c)
C.((a),b,c) D.((a,b,c))
8.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为( )
A.470 B.471
C.472 D.473
9.二叉树中第5层上的结点个数最多为( )
A.8 B.15
C.16 D.32
10.下列编码中属前缀码的是( )
A.{1,01,000,001} B.{1,01,011,010}
C.{0,10,110,11} D.{0,1,00,11}
11.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是( )
A.有向完全图 B.连通图
C.强连通图 D.有向无环图
12.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( )
A.O(1) B.O(logn)
C.O(n) D.O(n logn)
13.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( )
A. B.
C. D.n
14.对于哈希函数H(key)=key%13,被称为同义词的关键字是( )
A.35和41 B.23和39
C.15和44 D.25和51
15.稠密索引是在索引表中( )
A.为每个记录建立一个索引项 B.为每个页块建立一个索引项
C.为每组记录建立一个索引项 D.为每个字段建立一个索引项
二、填空题（每小题2分，若有两个空格，每个空格1分，共20分）
16.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。
17.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作________。
18.已知链栈的结点结构为 栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为________和________。
19.空串的长度是________；空格串的长度是________。
20.假设一个6阶的下三角矩阵B按列优先顺序压缩存储在一维数组A中，其中A［0］存储矩阵的第一个元素b11,则A［14］存储的元素是________。
21.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。
22.如图所示的有向无环图可以排出________种不同的拓扑序列。
23.利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(________)。
24.对长度为20的有序表进行二分查找的判定树的高度为________。
25.在多重表文件中，次关键字索引的组织方式是将________的记录链接成一个链表。
三、解答题(每小题5分，共20分)
26.对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。
单链表和单循环链表的结点结构为
双向链表的结点结构为
(1)单链表
(2)单循环链表
(3)双向链表
27.假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。
28.当采用邻接表作为图的存储结构时，也可将邻接表中的顶点表由顺序结构改为链表结构。
(1)请分别画出这种邻接表的顶点链表结点和边表结点，并说明结点中各个域的作用；
(2)对如图所示的有向图画出这种邻接表。
29.已知4阶B-树如图所示。
(1)分别画出将关键字23和89相继插入之后的B-树。
(2)画出从插入之前的B-树中删除关键字51之后的B-树。
四、算法阅读题(每小题5分，共20分)
30.阅读下列函数algo,并回答问题：
(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)后的队列q；
(2)简述算法algo的功能。
void algo(Queue *Q)
{
Stack S;
InitStack(&S);
while (!QueueEmpty(Q))
Push(&S, DeQueue(Q));
while (! StackEmpty(&S))
ＥnQueue(Q,Pop(&S));
}
(1)
(2)
31.阅读下列函数F，并回答问题：
(1)已知如图所示的二叉树以二叉链表作存储结构，rt为指向根结点的指针。写出执行函数调用F(rt)的输出结果。
(2)说明函数F的功能。
void F(BinTree T)
{
Stack S;
if(T)
{
InitStack(&S);
Push(&S,NULL);
while(T)
{
printf("%c", T->data);
if(T->rchild) Push(&S,T->rchild);
if(T->lchild)T=T->lchild;
else T=Pop(&S);
}
}
}
(1)
(2)
32.已知邻接表的顶点表结点结构为
边表结点EdgeNode的结构为
下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。
int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型
{
int dgree, j;
EdgeNode *p;
degree= (1) ;
for(j=0;j<G->n;j++)
{
p=G->adjlist［j］. firstedge;
while ( (2) )
{
if( (3) )
{
degree++;
break;
}
p=p->next;
}
}
return degree;
}
(1)
(2)
(3)
33.已知单链表的结点结构为
下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。
请在空缺处填入合适的内容，使其成为完整的算法。
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
(1)
(2)
(3)
(4)
五、算法设计题(本题10分)
34.设线性表A=(a1,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，对A进行调整，使得当n为奇数时A=(a2,a4,…,an-1,a1,a3,…,an)，当n为偶数时A=(a2,a4,…,an,a1,a3,…,an-1)。
考试问吧
