2003年1月份全国高等教育自学考试数据结构导论试题

一、单项选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。错选、多选或未选均无分。每小题2分，共30分）

　　1.下列数据结构中，（ ）不都是线性结构。

　　A.栈和队列 B.队列和数组

　　C.数组和串 D.文件和队列

　　2.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用（ ）方式。

　　A.顺序存储 B.链式存储

　　C.索引存储 D.散列存储

　　3.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，则删除双链表中指针s所指结点的操作为（ ）

　　A.s->t1->r1=s->t1；s->r1->t1=s->r1；

　　B.s->t1->r1=s->r1；s->r1->t1=s->t1；

　　C.s->r1=s->t1->r1；s->t1=s->r->t1；

　　D.s->t1=s->t1->r1；s->r1=s->r->t1；

　　4.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指针s所指的新结点作为非空双链表中q所指地点（中间结点）的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是（ ）

　　A.q->right=s； s->left=q； q->right->left=s； s->right=q->right；

　　B.s->left=q； q->right=s； q->right->left=s； s->right=q->right；

　　C.s->left=q； s->right=q->right； q->right->left=s； q->right=s；

　　D.以上都不对

　　5.由下列三棵树组成转的森林换成一棵二叉树为（ ）

　　6.具有100个结点的完全二叉树的深度为（ ）

　　A.6 B.7 C.8 D.9

　　7.已知一个稀疏矩阵的三元组表如下：（1，2，3），（1，6，1），（3，1，5），（3，2，-1），（4，5，4），（5，1，-3），则其转置矩阵的三元组表中第3个三元组为（ ）

　　A.（2，1，3） B.（3，1，5） C.（3，2，-1） D.（2，3，-1）

　　8.无向图的邻接矩阵是一个（ ）

　　A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵

　　9.下列说法中正确的是（ ）

　　A.一个具有n个顶点的无向完全图的边数为n（n-1）

　　B.连通图的生成树是该图的一个极大连通子图

　　C.图的广度优先搜索是一个递归过程

　　D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量

　　10.顺序查找法与二分查找法对存储结构的要求是（ ）

　　A.顺序查找与二分查找均只适用于顺序表

　　B.顺序查找与二分查找既适用于顺序表，也适用于链表

　　C.顺序查找只适用于顺序表

　　D.二分查找只适用于顺序表

　　11.在开散列表上，每个地址单元所链接的同义词表（ ）

　　A.其键值相同 B.其元素值相同

　　C.其散列地址相同 D.其含义相同

　　12.散列文件中的记录通常成组存放，若干个记录组成一个存储单位，这个存储单位称为（ ）

　　A.磁道 B.块 C.柱面 D.桶

　　13.索引非顺序文件中的索引表是（ ）

　　A.非稠密索引 B.稠密索引

　　C.主索引 D.多级索引

　　14.对n个记录的文件进行堆排序，最坏情况下的执行时间为（ ）

　　A.O（log2n） B.O（nlog2n）

　　C.O（n） D.O（n2）

　　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

　　二、填空题（每小题2分，共26分）

　　请在每小题的空格中填上正确答案。错填、不填均无分。

　　16.下列程序段的时间复杂性的量级为_________.

　　for （i=1；i

　　for（j=i；j

　　date

　　next

　　t=t+1

　　17.设某非空单链表，其结点形式为 ， 若要删除指针q所指结点的直接后继结点，则需执行下列语句序列：

　　p=q->next；________；free（p）；

　　18.队列可以看成是一种运算受限制的线性表，也称为______线性表。

　　19.链栈的类型定义如下：

　　typedef struct node

　　{ DateType date；

　　struct node *next；

　　}LStackTp；

　　若栈非空，则退栈操作可以用下列算法片段实现：

　　p=ls；/* ls为栈顶指针*/

　　*x=p->date； /*栈顶元素通过参数返回*/

　　___________；

　　free（p）； /*释放原栈顶结点空间*/

　　20.在非空树上，_____没有直接前趋。

　　21.设有33个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有____个结点。

　　22.无向图中的连通分量定义为无向图的_________.

　　23.在开散列表上查找键值等于K的结点，首先必须计算该键值的______，然后再通过指针查找该结点。

　　24.对静态表顺序查找算法采用设置岗哨方式与普通的设置循环控制变量相比，进行一次查找所花费的平均时间大约减少_____.

　　25.若要对某二叉排序树进行遍历，保证输出的所有结点键值序列按递增次序排列，应对该二叉树采用_________遍历法。

　　26.文件的基本存取单位是_________.

　　27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素ai和ai+1的值，若ai的值大于ai+1的值，则交换ai和ai+1.如此反复，直到某一趟中没有记录需要交换为止，该排序方法被称为_________.

　　28.在插入排序、快速排列、堆排序、归并排序中，排序方法不稳定的有_________.

　　三、应用题（本大题共5小题，共30分）

　　29.现有一组单词（WEK，SUN，MON，TUE，WED，THU，FRI，SAT），其相应的散列函数值为（3，2，6，3，2，5，6，0），散列表长度为10（散列地址空间为0……9），要求：（6分）

　　（1）构造该闭散列表，并用线性探测法解决冲突；

　　（2）若对每个元素查找一次，求总的比较次数。

　　30.已知无向图G的邻接矩阵如下。假设对其访问时每行元素必须从右到左，请画出其所有的连通分量，并且写出按深度优先搜索时各连通分量的访问序列。（8分）

　　31.设要将序列（Q，H，C，Y，P，A，M，S，R）按字母升序排序，请画出采用堆排序方法时建立的初始堆及第一次输出堆顶元素后筛选调整以后的堆。（8分）

　　32.设二叉树后根遍历的结果为BCA，画出所有可得到这一结果的二叉树。（5分）

　　33.设有一循环队列sq.data［maxsize］，一般情况下队列中至多可存放多少个元素？为什么？（3分）

　　四、设计题（本大题共2小题，共14分）

　　34.设有两个按升序排列的单链表X和Y，其头指针分别为p，q结点结构说明如下：

　　typedef struct nodel

　　{

　　int data；

　　struct nodel *next

　　}node；

　　试设计一个算法void concat（node *p，*q）将它们合并成一个以p为头指针的单链表Z，使其仍然有序。（6分）

　　35.设有序表r长度为n，欲在表中查找键值为Kn的某元素。若查找成功，则返回该元素在有序表r中的位置，若不成功，则返回0值。用二分查找法，编写一算法完成上述操作，并给出该算法的平均查找长度。该有序表存储结构定义如下：（8分）

　　typedef struct

　　{ keytype key；

　　Elemtype data；

　　}rec；

　　typedef struct

　　{ rec item［maxsize+1］；

　　int n；

　　}sqtable；