西南交通大学 数据结构期末考试 .pdfVIP

一．填空题（每空1分）

1.在线性表的顺序存储中，元素之间的逻辑关系是通过元素在存储器中的相对位置

确定的；在线性表的链式存储中，元素之间的逻辑关系是通过指针确定的。

2.若长度为n的线性表采用顺序存储结构，则在其第i个位置插入一个新元素算法的时间

复杂度为O(n)。

3.线性表、栈和队列都是线性结构，可以在线性表的任意位置位置插入和删除元素；

对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和队头删

除元素。

k-1k

4.深度为K的完全二叉树至少有2个结点，至多有2-1个结点，若按自上而下、从

左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2k-1

二．选择题（每题2分）

1.线性表的顺序存储结构是一种A的存储结构，线性表的链式存储结构是一

种B的存储结构。

A．随机存取B．顺序存取C．索引存取D．散列存取

2.若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从

队列中删除一个元素，再加入两个元素后，rear和front的值分别为B。

A．1和5B．2和4

C．4和2D．5和1

3.设栈的输入序列为123…..n，输出序列为a,a,a,……,a，若存在1=k=n，使得a=n，

123nk

则当k=i=n时，a为D。

i

A．n-i+1B．n-(i-k)

C．iD．不确定

4.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法

___B_。

A正确B错误

5.在一非空二叉树的中序遍历序列中，根结点的右边__A___。

A只有右子树上的所有结点B只有右子树上的部分结点

C只有左子树上的部分结点D只有左子树上的所有结点

三改错题：

阅读下列算法，若有错，则改正之。

BiTreeInSucc(BiTreeq){

//已知q是指向中序线索二叉树上某个结点的指针，本函数返回指向*q的前驱的指针

r=q-lchild;

共3页第1页

if(!r-ltag)//改为：if(!q-ltag)

while(!r-ltag)r=r-lchild;//改为：while(!r-rrtag)r=r-rchild;

returnr;

}//InSucc

四、已知二叉树BT各结点的先序和中序序列分别是A、B、C、D、E、F、I、J、K、L和

C、B、A、E、D、I、F、L、K、J，请画出该二叉树，并写出其后序序列。

六．已知某系统在通信联络中只可能出现10种字符（从字母A到字母J），各字符出现的概

率分别为A(0.02)，B(0.03)，C(0.1)，D(0.19)，E(0.07)，F(0.08)，G(0.14)，H(0