北京工商大学818数据结构2001、2003历年考研真题汇编
● 摘要
北京工商大学2001
一．选择题
1． 对稀疏矩阵进行压缩存储目的是
A ．便于进行矩阵运算 B 。便于输入和输出
C ．节省存储空间 D 。降低运算的时间复杂度
2． 假设以数组A[m]存放循环队列的元素, 其头尾指针分别为front 和rear ，则当前队列
中的元素个数为
A ．(rear-front+m)%m B ．rear-front+1
C ．(front-rear+m)%m D ．(rear-front%m
3． 在一棵高度为h 的满二叉树中，结点总数为
A ．2k-1 B ．2k C ．2k -1 D ．Llog 2k 」+1
4. 若用冒泡排序对关键字{18,16,14,12,10,8},进行从小到大的排序，所需进行的关键字比较次数是
A ．10 B ．15 C ．21 D ．34
5．对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是
A ．head ==null B ．head →next ==null
C ．head →next ==head D ．head!=null
6．的长度是指
A ．串中所含不同字母个数 B 。串中所含字符个数
C ．串中所含不同字符个数 D ．串中所含非空格字符个数
7．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的节点个数是
A. 9 B.11 C.15 D. 不确定
8．下列四个序列中，那一个是堆
A. 75,65,30,15,25,45,20,10 B. 75,65,4510,30,25,20,15
C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15
9. 已知二叉树的前序徐列为ABDCEFG, 中序序列为DBCAFEG 则其后序序列为
A. DCBAFGE B.DCBFGEA C.DCBFEGA D.DCBGFEA
10. 在下面的程序段中，对x 的赋值语句的频度为
for i :=1 to n do
for j:=1 to n do
x:=x+1;
A. O(2n) B.O(n) C. O(n2) D.O(log2n)
二．填空题
1．假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素a 9,9在B 中的存储位置k= . （注：矩阵元素下标从1开始）
2．由五个分别带权值为{9，14，7，5，2}的叶子结点构造一棵哈夫曼树，则该树的带权路径长度为 。
3．当增量d=1时，该趟希尔排序与 排序基本一致。
4．在一个长度为n 的顺序表中第i 元素（1<=i<=n）之前插入一个元素时，需向后移动 个元素。
5．设有二维数组A[0..9,0..19],其每个元素占两个子结，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为 。
三．试利用广仪表取表头head(ls)和表尾为tail(ls)的基本运算，将原子d 从下列表中分解出
来，请写出每一步的运算结果。