课程代码：21049
适用专业：计算机应用、计算机网络
一、判断题 (每小题1分，共10分)
1.程序越短，程序运行的时间就越少。( )
2.一个程序流程图就是一个算法。( )
3.采用循环链表作为存储结构的队列就是循环队列。( )
4.堆栈是一种插入和删除操作在表的一端进行的线性表。( )
5.一个任意串是其自身的子串。( )
6.深度为h的二叉树共有2h-1个结点。( )
7.哈夫曼树一定是完全二叉树。( )
8.带权连通土中某一顶点到图中另一惦念的最短路径不一定唯一。( )
9.折半查找方法可以用于按值有序的线性链表的查找。( )
10.完全二叉树不一定是堆积。( )
二、单项选择题 (每小题2分，共10分)
1.在长度为n的线性表A[1:n]的第i个位置插入一个元素，需要后移_______个元素。( )
A.n-1 B.n-i+1
C.n-i-1 D.i
2.中缀表达式A-(B+C/D)*E的后缀形式是 ( )
A.AB-C+D/E* B.ABC+D/-E*
C.ABCD/E*+- D.ABCD/+E*-
3.具有n个结点的完全二叉树的深度为 ( )
(符号┗x┛表示取不大于x的最大整数)
A.┗log2n┛ B.┗log2n┛-1
C.┗log2(n+1)┛ D.┗log2n┛+1
4.具有n个顶点的无向图最多有_______条边。 ( )
A.n(n-1)/2 B.n(n+1)/2
C.n2/2 D.2n
5.根据堆积的定义，下列的四个序列中_______是一个堆积。 ( )
A.75 65 30 15 25 45 20 10
B.75 65 45 10 30 25 20 15
C.75 45 65 30 15 25 20 10
D.75 45 65 10 25 30 20 15
二、填空题 (每空2分，共20分)
1.数据结构课程研究的主要内容包括_____________、_____________、_____________三方面。
2.在长度为n的线性表A的第i个位置插入一个新元素的过程应该首先__________________________，然后__________________________，最后__________________________。(1≤n≤n+1)
3.若具有n个结点的二叉树采用二叉链表结构，则该链表中共有_____________个指针域，其中_____________个指针域用于链接孩子结点，_____________个指针域存放nil。
4.对具有n个元素的序列采用堆积排序法进行排序，排序趟数为_____________。
三、简答题 (每小题10分，共20分)
1.按照压缩存储的思想，对具有t个非零元素的m×n阶稀疏矩阵采用三元组表存放于数组B[1:(t+1),1:3]中，问:t达到什么程度时，这样做才有意义？
2.设某排序连续顺序文件的记录按关键字值的大小从小到大排列，请用文字叙述在该文件中采用折半查找方法确定一个记录存在与否的过程。
四、问题求解题 (每小题10分，共20分)
1.某航空公司在七个城市分别设有分公司V1,V2,V3,V4,V5,V6,V7，矩阵A中元素A[i,j]表示Vi到Vj的直达飞机票价(A[i,j]=∞表示Vi到Vj不直接通航)，试为该航空公司制作一张由V1到各分公司的最便宜的通航线路图。
┏ ┓
┃ 0 1000 200 ∞ ∞ ∞ ∞ ┃
┃1000 0 ∞ ∞ 100 ∞ ∞ ┃
┃ 200 ∞ 0 200 ∞ 1100 ∞ ┃
A=┃ ∞ ∞ 200 0 400 600 ∞ ┃
┃ ∞ 100 ∞ 400 0 ∞ 700 ┃
┃ ∞ ∞ 1100 600 ∞ 0 300 ┃
┃ ∞ ∞ ∞ ∞ 700 300 0 ┃
┗ ┛
2.已知某二叉树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，请画出该二叉树的前序线索二叉树的二叉链表表示。
六、算法题 (每小题10分,共20分)
1.下面是一个在长度为n的线性表A中删除值为item的所有元素的算法，请在算法的空缺处填入适当的内容，使之能正常工作。
procedure DEL(A,n,item)
i←1
while┏━━━━━━┓do
┗━━━━━━┛
if A[i]=item then
[for j←i+1 to n do]
A[j-1]←A[j]
end
┏━━━━━┓
┗━━━━━┛]
else
┏━━━━━┓
┗━━━━━┛
end
end
2.下面是将任意一个无符号十进制整数num转换为八进制整数的非递归算法，算法中用到一个链式存储结构的堆栈来暂存转换过程中的各位八进制数字，栈顶指针为top，敛结点的构造为data|link。请在算法的空白处添入适当内容，使之能够正常工作。
procedure CHANGE(num)
top←nil
while num≠0 do
call GETNODE(P) // 申请一个新的链结点 //
data(p)←num MOD 8 // 求num除以8的余数 //
┏━━━━━━━━━━┓ // 进栈 //
┗━━━━━━━━━━┛
┏━━━━━━━━━━┓
┗━━━━━━━━━━┛
num←num DIV 8 // 求num除以8的商 //
end
while┏━━━━━┓do // 若堆栈不空 //
┗━━━━━┛
print(data(top)) // 输出以为八进制数字 //
p←top
┏━━━━━━━━━━┓
┗━━━━━━━━━━┛ // 退栈 //
call RET(p) // 释放一个链结点 //
end
end
|
|
|
论坛热贴
