数据结构期末考试试题（含详细答案）
需积分: 50 128 浏览量
2013-06-30
15:11:21
上传
评论 7
收藏 233KB DOC 举报
“数据结构”期末考试试题
一、单选题(每小题 2 分，共 12 分)
1．在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行( )。
B
A． HL＝ps p 一>next＝HL
B． p 一>next＝HL；HL＝p3
C． p 一>next＝Hl；p＝HL；
D． p 一>next＝HL 一>next;HL 一>next＝p；
2．n 个顶点的强连通图中至少含有( )。B
A.n—l 条有向边 B.n 条有向边
C.n(n—1)／2 条有向边 D.n(n 一 1)条有向边
3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。C
A.O(1) B.O(n)
C.O(1Ogzn) D.O(n2)
4．由权值分别为 3，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权
路径长度为( )。D
A．24 B．48
C． 72 D． 53
5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最
好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。B
A.整形 B.引用型
C.指针型 D.常值引用型·
6．向一个长度为 n 的顺序表中插人一个新元素的平均时间复杂度为( )。A
A．O(n) B．O(1)
C．O(n2) D．O(10g2n)
二、填空题(每空 1 分，共 28 分)
1．数据的存储结构被分为——、——、——和——四种。
2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自
分别为——域和——域。
3．——中缀表达式 3 十 x*(2.4／5—6)所对应的后缀表达式为————。
4．在一棵高度为 h 的 3 叉树中，最多含有——结点。
5．假定一棵二叉树的结点数为 18，则它的最小深度为——，最大深度为——·
6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结
点的值，右子树上所有结点的值一定——该结点的值。
7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，
直到被调整到——位置为止。
8．表示图的三种存储结构为——、——和———。
9．对用邻接矩阵表示的具有 n 个顶点和 e 条边的图进行任一种遍历时，其时间
复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。
10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找 43 和
56 元素时，其查找长度分别为——和——·
11．假定对长度 n＝144 的线性表进行索引顺序查找，并假定每个子表的长度
剩余29页未读，继续阅读
资源评论
