微信小程序第I卷（选择题）
评卷人 得分
一、单项选择题：1～20小题。下列每题给出的选项中，只有一个选项是符合题目要求的。
1．数据的存储结构是指（ ）
A．数组类型
B．指针类型
C．数据之间的逻辑关系
D．数据之间的物理关系
2．下列关于CSMA／CD协议的叙述中，错误的是（ ）
A．边发送数据帧，边检测是否发生冲突
B．适用于无线网络，以实现无线链路共享
C．需要根据网络跨距和数据传输速率限定最小帧长
D．当信号传播延迟趋近0时，信道利用率趋近100％
3．判定一个栈S（最多有n个元素）为满的条件是（ ）。
A. S->top!=0
B. S->top= =0
C. S->top!=n
D. S->top= =n
4．3个进程共享4个互斥资源，则每个进程最多申请（ ）个资源时，系统不会死锁。
A．1
B．2
C．3
D．4
5．在使用浏览器浏览一个万维网网站时，通讯双方必须遵循的其中一个协议是（ ）
A．SMTP协议
B．Telnet协议
C．FTP协议
D．TCP协议
6．在平衡二叉树中，（ ）
A．任意结点的左右子树结点数目相同
B．任意结点的左右子树高度相同
C．任意结点的左右子树高度之差的绝对值不大于1
D．不存在度为1的结点
7．某计算机主存地址空间大小为256MB，按字节编址。虚拟地空间大小为4GB，采用页式存储管理，页面大小为4KB，TLB(快表)采用全相联映射，有4个页表项，内容如下表所示。
则对虚拟地址03FFF180H进行虚实地址变换的结果是（ ）
A．0153180H
B．0035180H
C．TLB缺失
D．缺页
8．n个结点的线索二叉树上含有的线索数为（ ）
A．n
B．2n
C．n-1
D．n+l
9．在系统内存中设置磁盘缓冲区的主要目的是（ ）
A．减少磁盘I/O次数
B．减少平均寻道时间
C．提高磁盘数据可靠性
D．实现设备无关性
10．线性表采用链式存储时，其地址（ ）。
A. 必须是连续的
B. 一定是不连续的
C. 部分地址必须连续
D. 连续与否均可以
11．假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点v相关的所有弧的时间复杂度是（ ）
A．O（n）
B．O（e）
C．O（n+e）
D．O（n*e）
12．一个有28条边的非连通无向图至少有（ ）个顶点。
A．7
B．8
C．9
D．10
13．由3 个结点可以构造出多少种不同的二叉树？（ ）
A．2
B．3
C．4
D．5
14．将两个长度为N的有序表归并到一个长度为2N的有序表，最少和最多需要比较的次数分别是（ ）
A．N，2N-1
B．N-1，2N
C．N，2N
D．N-1，2N-1
15．二维数组A的每个元素是由6个字符组成的串，其行下标i＝0，1，…，8，列下标j＝1，2，…，10。设每个字符占一个字节。若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时起始地址相同的元素是（ ）
A．A[8，5]
B．A[3，10]
C．A[5，8]
D．A[0，9]
16．下面关于Prim算法和KruskAl算法的时间复杂度正确的是（ ）
A．Prim算法的时间复杂度与网中的边数有关，适合于稀疏图
B．Prim算法的时问复杂度与网中的边数无关，适合于稠密图
C．KruskAl算法的时间复杂度与网中的边数有关，适合于稠密图
D．KruskAl算法的时间复杂度与网中的边数无关，适合于稀疏图
17．KMP算法的特点是在模式匹配时指示主串的指针（ ）
A．不会变大
B．不会变小
C．都有可能
D．无法判断
18．若对n阶对称矩阵A[1…n，1…n]以行序为主序方式将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B[1…fl(n+1)／2]中，则在B中确定aij(i＜j)的位置k的关系为（ ）
A．i×(i-1)／2+j
B．j×(j-1)／2+i
C．i×(i+1)／2+j
D．j×(j+1)／2+i
19．无向图中一个顶点的度是指图中（ ）
A．通过该顶点的简单路径数
B．通过该顶点的回路数
C．与该顶点相邻接的顶点数
D．与该顶点连通的顶点数
20．有向带权图如图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（ ）
A．d，e，f
B．e，d，f
C．f，d，e
D．f，e，d
第II卷（非选择题）
评卷人 得分
二、填空题：21～26小题。请将答案写在答题纸指定位置上。
21．算法的________性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到____________的输出结果。
22．在二叉树中，指针p所指结点为叶结点的条件是______。
23．在一棵有N 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为________。
24．在一个长度为n的顺序表中，向第i个元素（1≤i≤n）之前插入一个新元素时，需向后移动_______ 个元素。
25．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。
26．在 AOV网 中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。
评卷人 得分
三、应用题：27～30小题。请将答案写在答题纸指定位置上。
27．设有一个三维数组a[c1:d1，c2:d2，c3:d3]，其中ci:di是第i维的界偶，如该数组在内存中按行排列，且a[c1，c2，c3]的地址为a0，那么请导出下标变量a[i1，i2，i3]的地址，假设每个元素占L个单元。
28．在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?
29．请阅读下列算法，回答问题
PROCEDURE sort（r，n）
BEGIN
FOR i:=2 TO n DO
BEGIN
x:=r（i）；r（O）:=x；j:=i-1；
WHILE x.key<r（j）.key DO
BEGIN
r（j+1）:=r（j）； j:=j-1
END；
r（j+1）:=x
END
END；
问题一：这是什么类型的排序算法，该排序算法稳定吗？
问题二：设置r（O）的作用是什么？若将WHILE—DO 语句中判断条件改为x.key<=r（j）.KEY，该算法将会有什么变化，是否还能正确工作？
30．M 叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应？
评卷人 得分
四、程序填空：31～32小题。请将答案写在答题纸指定位置上。
31．后序遍历二叉树的非递归算法，bt是二叉树的根，S是一个栈，maxsize是栈的最大容量。
TYPE bitreptr=^bnodetp；
bnodetp=RECORD data:datatype； lchild，rchild:bitreptr END；
TYPE stacktyp=RECORD data:ARRAY[1..maxsize] OF bitreptr；top：0..maxsize；END；
PROCEDURE posterorder（bt：bitreptr）；
BEGIN S.top:=0；p:=bt；
REPEAT
WHILE p<>NIL DO BEGIN S.top:=S.top+1； IF S.top>maxsize THEN stackfull
ELSE BEGIN S.data[S.top]:=p； （1）__； END
END；
IF S.data[S.top]^.rchild<>NIL THEN （2）__
ELSE BEGIN REPEAT write （S.data[S.top]^.data）； S.top=S.top-1；
UNTIL S.top=0 OR S.data[S.top]^.rchild<>S.data[S.top+1]；
IF S.data[S.top]^.rchild<>S.data[S.top+1] THEN （3）__；
END；
UNTIL（4）___；
END；
32．假设链表p和链表q中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的值为max,且链表中其他结点的值都小于max，在程序中取max为9999。在各个链表中，每个结点的值各不相同，但链表p和链表q可能有值相同的结点（表头结点除外）下面的程序将链表q合并到链表p中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填一个语句或一个表达式，链表的结点类型如下
TYPE nodeptr=^nodetype；
nodetype=RECORD
data：integer； link：nodeptr;
END；
CONST max=9999;
PROCEDURE merge（VAR p:nodeptr;q:nodeptr）;
VAR r,s: nodeptr;
BEGIN
r:=p;
WHILE （A）___ DO
BEGIN
WHILE r^.link^.data<q^.link^.data DO （B）___;
IF r^.link^.data>q^.link^.data
THEN BEGIN s:=（C）_; （D）_:=s^.link; s^.link:=（E）_; （F）_ _:=s; （G）_; END
ELSE BEGIN （H）__; s:=q^.link; （I）__; dispose（s） END
END;
dispose（q）
END;
评卷人 得分
五、算法设计题：33～34小题。请将答案写在答题纸指定位置上。
33．输入N个只含一位数字的整数，试用基数排序的方法，对这N个数排序。
34．已知二叉树排序树中某结点指针p，其双亲结点指针为fp，p为fp的左孩子，试编写算法，删除p所指结点。
点点赞赏，手留余香
给TA打赏
请先 ！