一、 单选题（每小题1分，共10分）
1．与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。 A．存储结构 B.逻辑结构 C.算法 D.操作 2.链式栈与顺序栈相比，一个比较明显的优点是（ ）。 A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便
3．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ ）。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序
4．若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ ）。 A.上三解矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵
5．在一个顺序存储的循环队列中，队头指针指向队头元素的（ ）。
A.前一个位置 B.后一个位置 C.队头元素位置 D.队尾元素的前一位置 6．用链表表示线性表的优点是（ ）。
A.便于随机存取 B.花费的存储空间比顺序表少
C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同
7．对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较。 A.8 B.10 C.15 D.25
8.下列存储形式中，（ ）不是树的存储形式。
A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 9．在一棵具有5层的满二叉树中结点总数为（ ）。 A.31 B.32 C.33 D.16
10.设有100个数据元素，采用折半搜索时，最大比较次数为（ ）。 A.6 B.7 C.8 D.10
二、 判断题（判断下列各个叙述的正误。对，在题号前的括号内填入“√”；错，在题号
前的括号内填入“×”。每小题1分，共10分）
（ ）1、算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算。要想准确地计算总运算时间是不可行的。
（ ）2、二维数组是数组元素为一维数组的线性表，因此它是线性结构。 （ ）3、顺序表用一维数组作为存储结构，因此顺序表是一维数组。 （ ）4、通常使用两个类来协同表示单链表，即链表的结点类和链表类。 （ ）5、栈和队列都是顺序存取的线性表，但他们对存取位置的不同。
（ ）6、在使用后缀表示实现计算器类时用到一个栈的实例，其作用是暂存运算对象。 （ ）7、具有n个结点的完全二叉树的高度为「log2n」+1。（n≥0，根在第0层） （ ）8、为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。 （ ）9、闭散列法通常比开散列法时间效率更高。
（ ）10、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。 三、 阅读理解题（说明下列递归过程的功能，10分）
void unknown(BinTreeNode*T, int a[ ],int i ){ //指针T是完全二叉树的根指针。 If(T! =NULL){ A[i]=T->data;
Unknown(T->leftChild,a,2*i+1);
Unknown(T->rightChild, a,2*i+2); } }
主程序调用方式unknown(BT.root,a,0);
//将完全二叉树所有结点从根开始，自顶向下，同一层自左向右连续编号， //根结点的编号为0。 四．简答题（共25分）
1． 对下面的带权无向图采用prim算法从顶点①开始构
造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）（5分）
S: 顶点号 Edge: (顶点，顶点，权值) ① ① ① ① ① ① （ ， ， ） （ ， ， ） （ ， ， ） （ ， ， ） （ ， ， ）
2． 某二叉树的结点数据采用顺序存储表示如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1718 19 E
(1) 试画出此二叉树的图形表示。（3分）
A F D H C G I B (2) 写出结点D的双亲结点及左、右子女。（3分）
(3) 将此二叉树看作森林的二叉树表示，试将它还原为森林 。（3分） 3． 设待排序序列为{10，18，4，3，6，12，1，9，15，8}，请给出用希尔排序每
一趟的结果。增量序列取为5，3，2，1。（每一趟2分，共8分） 4． 设散列表的长度为13，散列函数为H(k)=k%13,给定的关键码序列为19，14，23，
01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（3分）
0 1 2 3 4 5 6 7 8 9 10 11 12
四、 综合算法题（每小题5分，共15分） 对于二维整数数组A[m][n],对下列三种情况，分别编写相应的函数。
（1） 求数组所有边缘元素的和。（5分）
int sum1(int A[M][N],int m,int n)//M和N分别大于等于m和n { }
(2)求从A[0][0]开始的互不相邻的所有元素的和。（5分） 注：一个元素的八个方向上的第一个元素均为相邻元素。 Int sum2 (int A[M][N],int m ,int n) { } （3） 假定m=n，请分别计算正、反两条对角线上的元素的和。（5分）
int sum3(int A[M][N],int n) { }
六、填空题（每空2分，共10分）
已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。下面的算法的功能是：从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。此算法有5处缺失，请根据算法的功能补充之。（10分）
#include typedef struct node{ int data;struct node*leftChild,*rightChild; }BintreeNode;
typedef BintreeNode * BinaryTree;
void ConstructTree(int T[],int I,BintreeNode * & ptr); int main(void){
BinaryTree t;int n;
Cout<<”Please enter the number of node :\\n”;cin>>n; Int *A=new int[n];
For(int I=0;IConstructTree(A,n,0,t); //以数组建立一棵二叉树 ——②————；//删除数组A return 1; }void ConstructTree(int T[],int n,int I,BintreeNode * &ptr) {
if (I>=n)_____③____;//置根指针为空 else
ptr=new BintreeNode;
ptr->data=T[I];
ConstructTree(T,n,2*I+1,____④________);
ConstructTree(T,n,___⑤________,ptr->rightChild); } }
缺失的语句为： ① ② ③
④ ⑤
七 为了计算表达式的值：( 30分)
（1）把栈Stack类型定义为带模板的类类型，该类中包括顺序存储的栈和对栈的每一种基本操作的实现；
（2）把进行后缀表达式求值的Compute算法改写为使用Stack类的算法；
（3）把进行中缀表达式转换为后缀表达式的Change算法改写为使用Stack类的算法；
成都东软信息技术学院
200 ~200 学年第 学期期末试题--数据结构(C语言)
题号 一 二 三 四 五 六 总分
分数
本课程为闭卷考试，试卷共六道大题，试卷满分100分，考试时间120分钟。
一．选择题（10×2分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不
选均不给分。
1．组成数据的基本单位是（C ） Ａ．数据项 Ｂ．数据类型 C．数据元素 D．数据变量 2．下面程序段的时间复杂度为（ D ）。
for(i=1;i<=n;i++) for(j=i;j<=n;j++)
s++;
A．O(1) B．O(n) C．O(n ) D．O(n )
3．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（ B ）
个元素。
A．n-i B．n-i+1 C．n-i-1 D．i
4．设单链表中指针p指向结点A，若要删除A后的结点且该结点存在，则需要修改指针的操作为（ A ）。
A．p->next=p->next->next B．p=p->next C．p=p->next->next D．p->next=p
5．若让元素1，2，3依次进栈，则出栈次序不可能出现（C ）种情况。
A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2
6．在一个循环顺序队列中，队首指针指向队首元素的（ C ）位置。
A、当前 B、后面 C、前一个 D、后一个
7．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是（ D ）。
A、front==NULL B、front!=NULL C、rear!=NULL D、front==rear 8．二叉树第i(i≥1)层最多有（ B ）个结点。
A．2i B． 2i-1 C．2i D．2i -1
9．如果结点A有3个兄弟，而且B为A的双亲，则B是度为（ A ）
Ａ．4 Ｂ．3 C．5 D．1
10．当待排序序列的关键码是随机分布时，下列哪种排序算法的平均时间复杂度最优（ C ）。
A．直接插入排序 B．直接选择排序 C．快速排序 D．冒泡排序 二．填空题（30分）：每空2分
1. 数据的逻辑结构被分为 I集合 、 树形结构 、 图形结构 和 线性结构 四种。 2．在一个长度为n的顺序表中插入一个元素，最少需移动 0 个元素，最多需移动__n______个元素。 3．双向循环链表的优点是 既可以方便的找到后继结点又可以方便的找到前驱结点。
4．队列的原则是 先进先出 。
5．顺序存储的队列如果不采用循环方式，则会出现 假溢出 问题。
6．具有个结点的完全二叉树的深度为 7 。
7．设一颗完全二叉树共有50个叶子结点，则它共有____49____个度为2的结点。
8．二叉树采用__中___序遍历可以得到结点的有序序列。
9．在一个具有n个顶点的无向完全图中，包含有 n(n-1)/2 条边，在一个具有n个顶点的有向完全图
中，包含有 n(n-1) 条边。
10．快速排序算法在最差的情况下其时间复杂度是 O(n2)。 。
三．判断题（5×2分）
1．任意一棵满二叉树一定也是完全二叉树。( ) 2．进栈操作时，必须判断栈是否已满。( )
3．一个程序的时间复杂度是指该程序运行时间与问题规模的对应关系。( )
4．采用链式结构存储线性表时，其地址可以是不连续的。( )
5．折半查找法的前提之一是线性表有序。( ) 1．√；2．×；3．√；4．√；5．√
四．应用题（4×5分）
1． 试比较顺序存储和链式存储的优缺点。（5分）
顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效率低。
2． 简述栈和队列这两种数据结构的相同点和不同点。（5分）
栈和队列都是操作受限的线性表。栈是先进后出，操作在一端进行；队列是先进先出，插入在一端，删除
在另一端进行。
3． 已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，试画出这棵二叉树。（5
分）
4． 对于给定的一组关键码：83，40，63，13，84，35，画出用冒泡排序对上述序列进行操作的各趟结果。
（5分）
83 40 63 13 84 35 13 83 40 63 35 84 13 35 83 40 63 84 13 35 40 83 63 84 13 35 40 63 83 84 13 35 40 63 83 84
五．算法设计题（20分）
1．编写算法，将任意十进制数转换成其他进制，要求写出完整代码，可采用顺序栈或链栈实现。（12分）
2．编写一算法完成瑟夫生死者游戏。（8分）
瑟夫生死者游戏的描述：N个旅客同乘一条船，因为严重超载，加上风浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并拟定N个人围成一圈，由第一个人数起，依次报数，数到第r人，便把他投入海中，然后再从他的下一个人数起，数到第r人，再将他仍进海里，如此循环的进行，直到剩下N/2个乘客为止。问哪些位置是将被扔下大海的位置。
