学海网

四川大学《数据结构与算法分析》试题及答案
选择题（每小题1分，共10分）
1. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。
A. O(n) B. O(n/2) C. O(1) D. O(n2)
2.带头结点的单链表first为空的判定条件是：
A. first == NULL; B. first->link == NULL;
C. first->link == first; D. first != NULL;
3. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。
A. n-2 B. n-1 C. n D. n+1
4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ ），在被调用程序中可直接操纵实际参数。
A. 空间 B. 副本 C. 返回地址 D. 地址
5.在一棵树中，（ ）没有前驱结点。
A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点
6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。
A. 2 B. 1 C. 0 D. –1
7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。
A. 20 B. 18 C. 25 D. 22
8.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( )
A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B.在第i个结点后插入一个新结点（1≤i≤n） C.删除第i个结点（1≤i≤n）
D.将n个结点从小到大排序
9.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n， 则pi为( )
A.i B.n=i C.n-i+1 D.不确定
10.数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为( )
A.r－f; B.（n＋f－r）% n; C.n＋r－f; D.（n＋r－f）% n

二、填空题（每小题1分，共10分）
1. 二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。
2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中， A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_________行的元素。
3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值
。。。。。