数据结构试题
说明：在有数据类型定义和算法设计的各题中，任取C语言、PASCAL语言之一作答，但不许使用所谓“类C”或“类PASCAL”。
一、选择题(从下列各题四个备选答案中选出一至四个正确答案，将其代号(A，B，C，D)写在题干前面的括号内。答案选错或未选全者，该题不得分。每小题1分，共计20分)
( )1．一个算法具有 等特点。
A．可行性 B．至少有一个输入量
C．确定性 D．健壮性
( )2. 是一个线性表。
A．(A，B，C，D) B．{’A’，’B’，’C’，’D’}
C．(1，2，3，…) D．(40，-22，88)
( )3．可使用 作压缩稀疏矩阵的存储结构。
A．邻接矩阵 B．三元组表
C．邻接表 D．十字链表
( )4．采用一维数组表示顺序存储结构时，可用它来表示 。
A．字符串 B．2度树 C．二叉树 D．无向图
( )5．假设进入栈的元素序列为d，c，a，b，e，那么可得到出栈的元素序列 。
A．a，b，c，d，e B．a，b，e，d，c
C．d，b，a，e，c D．d，b，a，c，e
( )6．对队列的操作有 。
A．在队首插入元素 B．删除值最小的元素
C．按元素的大小排序 D．判断是否还有元素
( )7．假设有60行70列的二维数组a[1．．60，1．．70]，以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32，58]的存储地址为 。(无第0行第0列元素)
A．16902 B．16904
C．14454 D．答案A，B，C均不对
( )8. 是C语言中"abcd321ABCD"的子串。
A．abed B．32lAB C．”abeABC” D．”2lAB”
( )9．在下列各广义表中，长度为3的广义表有 。
A．(a，b，c，()) B．((g)，(a，b，c，d，f)，())
C．(a，(b，©)) D．((()))
( )10．一个堆(heap)又是一棵 。
A．二叉排序树 B．完全二叉树
C．平衡二叉树 D．哈夫曼(Huffman)树
( )11．折半查找有序表(4，6，10，20，30，50，70，88，100)，若查找元素58，则它将依次与表中元素 比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70
C．20，50 D．30，88，50，70
( )12．对27个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。
A．3 B．4 C．5 D．6
( )13．具有12个结点的完全二叉树有 。
A．5个叶子 B．5个度为2的结点
C．7个分支结点 D．2个度为1的结点
( )14．具有n(n>0)个结点的完全二叉树的深度为 。
A．log2(n) B．log2(n+1)
C．log2(n)+1 D．loge(n) +1
( )15．用5个权值{3，2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是 。
A．32 B．33 C．34 D．15
( )16．对14个记录的表进行2路归并排序，共需移动 次记录。
A．42 B．56 C．91 D．84
( )17．对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是 。
A．O(n) B．O(n2) C．O(nlog2n) D．O(2n)
( )18．在最好情况下，下列算法中 排序算法所需比较关键字次数最少。
A．冒泡 B．归并 C．快速 D．直接插入
( )19．置换选择排序的功能是 。
A．选出最大的元素 B．产生初始归并段
C．产生有序文件 D．置换某个记录
( )20．可在 构造一个散列文件。
A．内存 B．软盘 C．磁带 D．硬盘
二、试用2种不同表示法画出下列二叉树B1的存储结构，并评述这2种表示法的优、缺点。(共10分)
二题图B1
三题图G
三、对图G：
1．从顶点A出发，求图G的一棵深度优先生成树；
2．从顶点B出发，求图G的一棵广度优先生成树；
3．求图G的一棵最小生成树。(共12分)
四、设哈希(Hash)函数为：H(k)=kMODl4，其中k为关键字(整数)，MOD为取模运算，用线性探测再散列法处理冲突，在地址范围为0~14散列区中，试用关键字序列(19，27，26，28，29，40，64，21，15，12)造一个哈希表，回答下列问题：
1．画出该哈希表的存储结构图；
2．若查找关键字40，必须依次与表中哪些关键字比较大小？
3．假定每个关键字的查找概率相同，试求查找成功时的平均查找长度。(共13分)
五、给定头指针为ha的单链表A，和头指针为hb的递增有序单链表B。试利用表A和表B的结点，将表A和表B归并为递增有序表C，其头指针为hc，允许有相同data值(数据元素)的结点存在，表A，B，C均带表头结点。
例如，给定：
将它们归并为：
1．在下列C算法merge中有下划线的位置填空，使之成为完整的算法，要求在填空后加注释，以提高算法的可读性。
2．假定单链表A和B的长度分别为m和n(m>0，n>0)，试分别就最好情况、最坏情况和平均性能，分析算法merge的时间复杂度。(共15分)
结点类型定义如下：
struct node 、
{ int data；
struct node next；
}；
算法如下：
Void merge(struct nodeha，struct node hb，struct nodehc)
{ struct node *pc，*qc，*pa，*fa；
int search；
hc=hb； hb=NULL；
pa=ha->next； free(ha)；
while(pa)
{pc=hc； qc=hc->next；
search= ；
while(qc&&search)
{if(pa->data<=qc->data)
；
else
{ pc=qc；
qc= ；
}
}
fa= ；
pa= ；
fa->next= ；
；
}
}
六、设下图二叉树B2的存储结构为二叉链表，root为根指针，结点结构为：(1child，data，rchild)其中：lchild，rchild分别为指向左右孩子的指针，data为字符型。(共10分)
1．对下列二叉树B2，执行下列算法traversel(root)，试指出其输出结果；
2．假定二叉树B2共有n个结点，试分析算法traversal的时间复杂度。结点类型定义如下：
struct node
{ chardata；
struct node *lchild，*rchild；
}；
算法如下：
void traversal(struct node *root)
{ if(root)
{ prinft(“%c”，root->data)；
traversal(root->lchild)；
prinft(”%c”，root->data)；
traversal(root->rchild)；
}
}
二叉树B2
七、算法设计题(要求：(1)写出所用数据结构的类型定义和变量说明；(2)写出算法，并在相关位置加注释，以提高算法的可读性。)
1．试设计一算法：输入一个有m行n列的整数矩阵，然后将每一行的元素按非减次序输出。例如，若输入：
4，3，5，6，2
9，8，1，2，8
7，1，2，3，8
则输出如下结果：
2，3，4，5，6
1，2，8，8，9
1，2，3，7，8
2．如果字符串的一个子串(其长度大于1)的各个字符均相同，则称之为等值子串。试设计一算法：输入字符串S，以’!’为结束标志，如果串S中不存在等值子串，则输出信息：”无等值子串”，否则求出(输出)一个长度最大的等值子串。
例如，若S=”abcl23abcl23！”，则输出：”无等值子串”；
又如，若S=”abcaabcccdddddaaadd!”，则输出等值子串：”ddddd”。(共20分)
