模拟试卷6
- 格式：doc
- 大小：44.00 KB
- 文档页数：5
《数据结构》模拟题六
一、单选题（每小题2分，共8分）
1．若需要利用形参直接访问实参，则应把形参变量说明为（）参数。
A．指针 B. 引用
C．值
2．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则
执行（）。
A. q->next=p->next;p->next=q;
B. p->next=q->next;q=p;
C. q->next=p->next;p->next=q;
D. p->next=q->next;q->next=p;
3.在一个顺序队列中，队首指针指向队首元素的（）位置。
Ａ.后一个Ｂ.前一个
Ｃ.当前
４.向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。
Ａ.O（log2n） B. O(n)
C. O(1)
D. 0(nlog2n)
二、填空题（每空1分，共32分）
1.数据的存储结构被分为________________、______________、________________和
______________四种。
2.对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入
元素的时间复杂度为________________。
3.在稀疏距阵所对应的三元组线形表中，每个三元组元素按____________为主序，
__________为辅序的次序排列。
4.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为
________________域和______________域。
5.中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为______________。
6.在一棵高度为h的3叉树中，最多含有_______结点。
7.假定一棵二叉树的结点数为18，则它的最小深度为________，最大深度为_______。
8.在一棵二叉搜索树中，每个分支结点的左子树上所有的结点的值一定___________该结
点的值，右子树上所有结点的值一定__________该结点的值。
9.当向一个小根堆插入一个具有最一小值的元素时，该元素需要逐层_______调整，直到
被调整到_______位置为止。
10.表示图的三种存储结构为_________________、________________和________________。
11.对用邻接距阵表示的具有n个顶点和e条边的图形进行任一种遍历时，其时间复杂度为
__________，对用邻接表表示的图进行任一种遍历时，其时间复杂度为______________。
12.从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查
找长度分别为___________和__________。
13.假定对长度n=144的线性表进行索引查找，并假定每个子表的长度均为n,则进行索引
查找的平均查找长度为__________，时间复杂度为___________。
14.一棵B-树中的所有叶子结点均处在_____________上。
15.每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫
做_______排序；每次从无序表中挑选出一个最大或最小元素，把它交换到有序表中的一端，此种排序方法叫做_________排序。
16.快速排序在平均情况下的时间复杂度为___________，在最坏情况下的时间复杂度为
__________。
三、运算题（每小题6分，共24分）
1．假定一棵普通树的广义表表示为a(b(e),c(f(h,i),g),d),分别写出先根，后根，按层遍历的结果。
先根：
后根：
按层：
2．已知一个带权图的顶点集V和边集G分别为：
V={0，1，2，3，4，5，6，7}；
E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9}；
则求出该图的最小生成树的权。
最小生成树的权：
3．对于线性表（18，25，63，50，41，32，90，66）进行散列存储时，若选用H（K）=K%11作为散列函数，则散列地址为0的元素有______个，散列地址为3的元素有______个，散列地址为8的元素有______个。
4．假定一组记录的排序码为（46，79，56，38，40，80，25，34），在对其进行快速排序的过程中，进行第一次划分后得到的排序码序列为________________________________。
四、阅读算法，回答问题（每小题8分，共16分）
1、void AD(Lnode* & HL)
{
Insert(HL,30);
Insert(HL,50);
Delete(HL,26);
Delete(HL,55);
}
假定调用该算法时以HL为表头指针的单链表中的内容为（15，26，48，55），则调用返回后该单链表中的内容为：
______________________________。
2、void AI(adjmatrrix GA,int i,int n)
{
cout<<i<<’’;
visted[i]=true;
for(int j=0;j<n;j++)
if(Ga[I][j]! =0&& GA[i][j]! =MaxValue&& ! visited[j])
AI(GA,j,n);
}
该算法的功能为：
_____________________________________________________________________。
五、算法填空，在画有横线的地方填写合适的内容（10分）
此为向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。
Void Insert(BtreeNode*&BST,const ElemType&item)
{
if(BST==NULL)
{ BTreeNode* p=new BTreeNode;
p->date=item;
______________________________;
BST=p;
}
else if(item<BST->date) ___________________________;
else______________________________;
}
六、编写算法（10分）
编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i的值进行有效性检查，同时不需要检查存储空间是否用完。
Void Insert(List& L，int i, ElemType x)
模拟题六答案及评分标准
（供参考）
一、单选题（每小题2分，共8分）
评分标准：填对者得2分，否则不得分。
1.B
2.D
3.B
4.A
二、填空题（每空1分，共32分）
评分标准：填对者得1分，否则不得分。
1. 顺序结构链接结构索引结构散列结构（次序无先后）
2 .O(n) O(1)
3. 行号列号
4. 值（或data）子表指针（或sublist）
5. 3 x 2.4 5 ／6 －*＋
6. (3 h-1)/2
7. 5 18
8. 小于大于
9. 向上堆顶
10. 邻接距阵邻接表边集数组（无次序先后）
11. O(n2) O(e)
12. 1 3
13. 13 O(n)
14. 同一层
15. 插入选择
16. O(nlog2n) O(n2)
三、选择题（每小题6分，共24分）
1. 先根：a,b,e,c,f,h,i,g,d;
后根：e,b,h,i,f,g,c,d,a:
按层：a,b,c,d,e,f,g,h,i
2. 最小生成树的权：34
3. 1 1 2 每个数据占2分
4.（40，34，25，38，46，80，56，79）
四、阅读算法，回答问题（每小题8分。
共16分）
1.（15，30，48，50）
评分标准：有一处错扣4分，两处及以上错8分全扣。
2. 从初始点v i出发深度优先搜索遍历由邻接距阵GA所表示的图
评分标准：请根据叙述情况酌情给分。
五、算法填空，在画有横线的地方填写合适的内容。
（10分）
p->left=p->right=NULL
Insert(BST->left，item)
Insert(BST->right，item)
评分标准：每空对给3分。
全对给10分。
六、编写算法（10分）
评分标准：请根据编程情况酌情给分。
vioid Insert(List& L,int i,ElemType x)
{
for(int j=L.size-1;j>=i-1;j--)
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++; }。
