计算机学科专业基础考研模拟卷三

1、计算机学科专业基础模拟卷三数据结构部分一、单项选择（10分，每题1分）1下面是有关抽象数据类型概念的论述，其中正确的说法是（ C ）。A 抽象数据类型与结构有关B 抽象数据类型与数据结构是同义词C 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作D 抽象数据类型是指描述客观事物且由计算机处理的数值、字符等符号的总称Page12下面是有关算法时间复杂度的论述，其中正确的说法是( A 算法的时间复杂度与数据规模无关B 算法的时间复杂度与算法的语句频度无关C 算法的时间复杂度与算法采用的解决问题的策略无关D 算法的时间复杂度与选择的程序设计语言无关D )。Page23.如果入栈序列为ABCD

2、, 不可能出现的出找序列是(B)A.ABCDC.ACDBB. DABCD. DCBAPage34假设某个循环队列借用数组Q06表示，如果当前的队头指针front和队尾指针rear分别为2和5。当首先执行一次出队操作，然后执行两次入队操作之后，队头指针front和队尾指针rear应该分别变为(C )A.4，6C.3，0B.0，3D.6，4Page45.如果在构造哈希表时采用链地址法解决，且哈希函数为H(key)=key MOD 8,则需要建造的链表数目是( C)A.6C. 8B. 5D. 9Page56.假设一棵完全二叉树含有456个结点，则度数为0、l、2的结点个数分别为( B)AC227,

3、1, 228228. 0, 228BD228, 1, 227不确定Page67.无向图的最小生成树是指(C).A.利用深度优先遍历得到的生成树 B.利用广度优先遍历得到的生成树 C.权值之和最小的生成树D.边的条数最少的生成树Page78.一棵高度为h的满二又树包含的结点总数为( B )A.2h-1C. log2hB.2h-1D.2hPage89在下列各种排序算法中，时间复杂度为O(nlog2n)且具有稳定性的是 ( C )A.快速排序C.归并排序B 堆排序D 直接排序Page910.在最好情况与法是（ D ）情况下，时间复杂度均为O(nlogn)且稳定的排序算A.快速排序C.堆排序B.冒泡排

4、序D.归并排序Page10二、填空题（20分，每题2分1.在采用顺序结构表示队列时，通常将其设计为循环队列.主要原因是（为了防止假上溢，充分利用空间）2.广义表GL=(a)，b)，d)，e)的深度是（5）Page113.己知两个递增有序的单链表(长度分别为m和n).如果将其归并成一个按元素递增有序的单链表，可能达到的最优时间复杂度为（m，n）Page124已知某棵二叉树的先序遍历序列为ABECDFGHIJK，中序遍历序列为 EBCDAGHFKJI，其后序遍历序列为（EDCBHGKJIFA）Page135树的后根遍历过程为（先依次后跟遍历每棵子树，然后跟节点）6如果在AOV网（用顶点表示活动的网

5、）中，包含一条由V 到V2的弧，则在拓扑序列中，顶点V 和顶点V2的排列关系是（ v 在v2之前）7.所谓树的遍历是指（按照某种规则依次树的节点）8.假设有向图的顶点个数为n，则该图最多包含的弧数为（n（n-1）Page149对于给定的有序表（1,5,9,14,33,42,46,63,76,79,83,99,102），如果采用二分查找，查找成功的平均比较次数为（41/13）10.在直接排序算法中，监视哨的作用为（防止数组越界,暂存数据）Page15三、简答题（40分，每题10分1.画出执行下列程序段之后链表的示意图.假设Lnode结构类型定义为:typedef struct nodedata;

6、struct node*next;Lnode;Page16/程序段L = new Lnode; p=L;for (i=1; idata=i*2;p-next=new Lnode; p=p-next;p-data=-1;p-next=NULL;24916-1Page172假设一段仅含有A，B，C，D，E，F这6个字母组成的西文文本，它们在文本中出的频率分别为：4%；10%；29%；24%；11%；22%试为其设计一组二进制编码，使得将这段西文文本编译后，所得到的二进制位数总长度最短，且在译码时不会产生二义性。要求：(l)阐述设计思路写出构造编码的具体过程写出最终结果，即为6个字母设计的二进制编码

7、Page18（1）设计赫夫曼树的（3）A：0110B：01 C：00 D：11 E: 010F：10Page193.已知图G含有8个顶点，它们之间的邻接关系用下列邻接矩阵Adj表示。Page20完成下列问题:写出“判断是否为无向图?”的代码片段按照深度优先和广度优先算法，写出从点出发，深度优先遍历和广度优先遍历这个图的遍历序列。（1）for（i=0；i8；i+）for（j=0；jleft）p=p-left;p-left=B;Page242.稀疏一元多项式是在工程项目中经常遇到的一种数学表示形式，其特点是:在一个最高幂次为n的一元多项式中，系数为零的项数很多。 例如： 10-20X100+90X

8、2000试为稀硫一元多项式的数据组织设计一种数据结构，并选择空间利用率高。且便于实现一元多项式基本运算的要求写出所设计的数据结构、选择的义，并简述其理由。结构。结构以及该结构的类型定Page25运用链表进行，结构的定义ADT Polynomial数据对象：数据关系：基本操作：ADT Polynomial 40页Typedef struct LnodeFloat ratio;/系数er；/幂 Struct Lnode *next；Lnode;Page26C语言程序设计部分一、阅读以下程序，写出输出结果，并且 题，作出相应的修改。（30分，每题10分）1. #include void main()

9、char ch,s=C Program; ch=getchar();这些程序设计中存在哪些问prf(%dn%sn,fun(s,ch),s);Page27fun(char *str,char ch) char *p;n=0;for(p=str;*p!=0;p+)if(*p!=ch)*str+=*p;elsen+;*str=0;return n;若程序运行时输入一个字符：r，请写出程序的运行结果2 C Pogam若再次运行程序，并输入一个字符：m，请写出程序的运行结果1 C Progra存在函数没有Page282.设当前路径下有文件file1.txt，其内容是“The best way to le

10、arn i work through and build some useful code”#include #define N 10void main()FILE *fp;char ch,strN; k=0;fp=fopen(file.txt,r);toPage29while(kN)请写出程序的运行结果Uifcftxbzch = fgetc(fp); if(ch=n)break; if(ch!= )strk+=ch+1;存在数组下边越界，while（kN-1）strk=0; fclose(fp);puts(str);Page303. #include #include void main()

11、i=0,*p;*(p+2)=i;i=p1; p1=p3; p3=i;for(i=0;i4;i+prf(%dt, i);p=(*)malloc(sizeof()*4);设输入12 23 34 45 ，请写出输出34 45 12 23while(ix thenPage32清空buf xn将line中的文本及其行号i添加到buf if n=x then将line中的文本及其行号i添加到buf ii+l重复执行第2)到11)步输出buf的所有内窖6)7)8)9)10)11)12)13)Page33(2)请用c语害编制程序，实现该算法(本小最15分) #include #include #include

12、 /缓冲区链表typedef struct node char line 256 ;num;struct node *next;Link;Page34/在表头添加元素Link* addHead( Link *p, char *line,i )Link *q = (Link *)malloc( sizeof( Link ) ); strcpy( q-line, line );q-num = i; q-next = p;return q;Page35整个链表Link* freelink( Link *p ) Link *q = NULL;for( ; p != NULL; p = q ) q = p-next;free( p );return NULL;/Page36main()i, n, max = 0;char line256; Link *buf = NULL;prf( Please input the text(end wiblline):nn );for( i=1; ; i+ )gets( line );/读入一行/空行时，结束循环if( 0 = (n = strlen( line ) ) )break;