安全检测:瑞星:安全 诺顿:安全 卡巴:安全
四川大学《数据结构与算法分析》试题及答案
选择题(每小题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.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为( )
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.链表对于数据元素的插入和删除不需移动结点,只需改变相关结点的________域的值
。。。。。