1、山东专升本计算机科学与技术（综合二）模拟试卷 2 及答案与解析单项选择题1 在一个单链表中，已知 p 所指向的是 q 所指向结点的前驱结点，若在 q 和 p 之间插入 s 所指向的结点，则执行( )。（A）s 一next=q 一next；q 一next=s（B） q 一next= 一 s 一next；s 一next=q（C） p 一next=s；s 一next=q（D）q 一next=s ；s 一next=p2 串是( ) 。（A）一些符号构成的序列（B）一些字母构成的序列（C）一个以上的字符构成的序列（D）任意有限个字符构成的序列3 数组 A1010的下标下界为 1，每个元素占 2 个字节，
2、存储在起始地址为 100的连续内存单元，则元素 A38的地址为( )。（A）138（B） 154（C） 111（D）1454 已知广义表 L=(x，y，z)，a，(u ，t，w)，则从 L 中取出原子项 y 的操作是( )。（A）head(tail(head(L)（B） head(head(tail(tail(tail(L)（C） head(tail(tail(tail(tail(L)（D）heacl(tail(tail(head(tail(L)5 已知完全二叉树有 80 个结点，则整个二叉树有( )个度为 2 的结点。（A）39（B） 41（C） 40（D）386 赫夫曼树中度为 1 的结点
3、个数为( )。（A）0（B） 1（C） 2（D）不确定7 具有 n 个顶点的有向完全图，边的总数为( )。（A）n（B） n(n 一 1)（C） n 一 1（D）n(n 一 1)28 二分查找法适用于存储结构为( )的，且按关键字排好序的线性表。（A）顺序存储（B）链接存储（C）顺序存储或链接存储（D）索引存储9 下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法是( ) 。（A）归并排序（B）直接插入排序（C）快速排序（D）起泡排序10 一个有向无环图的拓扑序列个数是( )。（A）1 个（B） 1 个或多个 （C） 0 个（D）多个填空题11 将下三角矩阵 A18，1
4、8的下三角部分逐行地存储到起始地址为 1000的内存单元中，已知每个元素占 4 个单元，则 A7，5的地址为_。12 若某二叉树有 20 个叶结点，有 30 个只有一个孩子的结点，则该二叉树的总结点数为_。13 如果以4，5，6，7， 8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。14 在顺序存储的二叉树中，编号为 i 和编号为 j 的结点处在同一层的条件是_。15 有一个有序表为1，3 ，9，12，32，41，45，62，75，77，82，95，100 ，当折半查找值为 82 的结点时，_次比较后查找成功。操作计算题15 已知一组关键字为19，14，23，1，68，20，84，27
5、，55，11，10，79)，设哈希函数为 H(ke3r)=key MOD13，哈希表的地址范围为 0 一 12 用线性探测再散列法处理冲突。完成问题：16 构造哈希表。17 假定每个关键字的查找概率相等，求查找成功时的平均查找长度 ASL。18 已知某字符串 s 中共有 8 种字符(a，b，c ，d，e ，f，g，h) 各种字符分别出现 2次，1 次，4 次，5 次，7 次，3 次，4 次，9 次。试把它们作为叶子结点的权值构造一棵哈夫曼树，并求出其带权路径长度(WPL) 。算法设计题19 试以单链表为存储结构实现简单选择排序的算法。应用题20 对单链表中元素按插入方法排序的算法如下，其中 L
6、 为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedef struct nodeint data；struct node*next；linknode，*link；void Insertsort(1ink L)link P，q， r，u；P=L 一next ； _；while(_)r=L；q=L 一 next；while(_b=b+1=1+1=2 ，此时 b 不等于 5，继续循环。a=0，b=2 时：a=ba=2 一 0=2;b=b+1=2+1=3，此时 b 不等于 5，继续循环。a=2 ，b=3 时：a=ba=32=1;b=b+1=3+1=4 ，此时 b 不等于 5，继续循环。
7、a=1，b=4 时：a=ba=41=3;b=b+1=4+1=5，此时 b 等于 5，停止循环。所以答案为 3。26 【正确答案】 120【试题解析】 函数 ff 在循环中调用 5 次，第一次调用 ff(1)，函数体执行，静态变量 f 的值为 1，执行 1*n，返回值为 1，第二次调用 ff(2)，静态变量 f 的值保留第一次调用的值 1，执行 1*n，返回值为 2，以此类推，第五次调用 ff(5)，f 保留第四次调用的值 24，执行 24*n=24*5=120，返回值为 120。27 【正确答案】 2 2【试题解析】 当函数调用时，其参数的传递是从右至左的。即先将+*t 传递给printf 函
8、数，此时，指针 t 指向字符数组的首位置，然后进行自加运算，1+1=2，因此字符 2 覆盖了原位置处的字符 1；当再将第二个参数*t 传递给printf 函数时，由于 t 仍然指向字符数组的首位置，而首字符已经变为 2，所以当按顺序输出时，其结果为：2，2。注意：函数参数的传递是从右至左的，但传递以后，执行结果仍然按顺序输出的。28 【正确答案】 ABCDBCDCDD【试题解析】 程序定义了一个字符数组 s，由给它所赋的字符串初值知，该数组只有五个元素。程序另定义了字符指针变量 p。循环开始时，先让 p 指向数组的首元素。循环每次输出以 p 所指字符为首字符的字符串，并让它指向下一个字符。如此
9、反复循环四次。程序设计题29 【正确答案】 #incl L1de“stdioh”void main( )int i，sum；int prime(int n)；*判断一个数是否为素数。不是，返回 0；是，返回 1*sum=0：for。(i=100；i=200；i+)if(prime(i)sum=sum+i：printf(“100 200 之间所有素数的和 sum=dn” ， sum)；getchar( )；int prime(int n)int k；for(k=2；k=n2；k+30 【正确答案】 main( )char stE20，*ps ；int i；printf(“input a string：n”)；ps=st：scanf(“s”，ps)；for(i=0；psi!=0；i+)if(psi=k)printf(“there is akin the stringn”) ：break； if(psi=0)printf(“There is nokin the stringn”)：
