2003年吉林省普通高等学校专升本教育考试

2003年吉林省普通高等学校专升本教育考试

计算机科学技术专业综合试卷

一、填空题

1．向栈中推入元素的操作是 。

2．线性表中结点的集合是 ，结点间的关系是 。 3．在双链表中要删除已知结点*p，其时间复杂度为 。 4．已知数组A[11][6]采用行序为主方式存储，每个元素占4个存储单元，并且数组元素A[0][0]的存储地址是1000，数组元素A[8][4]的地址是 。 5．在栈中存取数据遵从的原则是 。

6．广义表的长度是指 ，广义表的深度是指 。 7．N个顶点的连通图至少有 条边。

8．深度为k的完全二叉树至少有 个结点，至多有 个结点。 9．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 10．已知完全二叉树的第8层有8个结点，则其叶子结点数是 。

11．对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置，需比较 次。

12．拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成。 二、单项选择题

1．不带头结点的单链表head为空的判定条件是（ ）

A．head= =NULL B．head->next= =NULL C．head->next= =head D．head!=NULL

2．设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为（）

A．O(1) B．O(log2n) C．O(n) D．O(n2)

3．数组A中，每个元素A[i][j]的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[7][4]的起始地址为（）

A．SA+141 B．SA+144 C．SA+222 D．SA+225

4．某二叉树的后序遍历为dabec，中序遍历为debac，则前序遍历序列为（）

A．acbed B．decab C．deabc D．cedba

5．对于二叉树来说，第i层上至多有（）个结点。

A．2i B．2i-1 C．2i-1 D．2i-1-1

6．递归函数f(n)=f(n-1)+n (n>1)的递归体是（）

A．f(1)=0 B．f(0)=1 C．f(n)=f(n-1)+n D．f(n)=n

7．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A．1/2 B．1 C．2 D．4

8．已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）

A．0 3 2 1 B．0 1 2 3 C．0 1 3 2 D．0 3 1 2

9．对线性表进行二分查找时，要求线性表必须（）

A．以顺序方式存储 B．以链接方式存储

C．以顺序方式存储，且结点按关键字有序排列 D．以链接方式存储，且结点按关键字有序排列

10．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（）查找。

A．分块 B．顺序 C．二分 D．散列 11．设有1000个无序的元素，希望用最快的速度挑出其中前10个最大的元素，最好采用（）法。

A．冒泡排序 B．快速排序 C．堆排序 D．基数排序 12．非线性结构中，每个结点（）

A．无直接前趋

B．只有一个直接前趋和后继

C．只有一个直接前趋和个数不受限制的直接后继 D．有个数不受限制的直接前趋和后继 13．设高度为h的二叉树只有度为0和度为2的结点，则此类二叉树所包含的结点数至少为（）

A．2h B．2h-1 C．2h+1 D．h+1

14．矩阵是一个（）

A．对称矩阵 B．三角矩阵 C．带状矩阵 D．稀疏矩阵 15．散列文件是一种（）

A．顺序文件 B．索引文件 C．链接文件 D．计算寻址文件 三、假设二叉树包含的结点数据为1，3，7，2，12 1}画出两棵高度最大的二叉树

2）画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。

四、程序分析题 1．程序：

#include int x=1; main() {

func(x);

printf(“%d\\n”,x); }

func(int x) {

x=3; }

程序的执行结果是：

2．程序：

#include main() {

int a=2,*p,**PP; pp=&p; p=&a;

printf(“%d,%d,%d”,a,*p,**PP); }

程序的执行结果是：

3．程序：

#include main() {

char s[80],c1,c2=? ?; int i=0,num=0; gets(s);

while(s[i]!=?\\0?) {

c1=s[i]; if(i= =0) c2=? ?; else

c2=s[i-1];

if(c1!=? ? && c2= =? ?) num++; i++;

}

printf(“%d”,num); }

程序完成功能是：

4．下面的函数invert的功能是将一个字符串的内容颠倒过来。程序有一处错误请找出，度改正。 程序：

void invert(char str[]) {

int i,j,k;

for(i=0,j=strlen(str); i>j; i++,j--) {

k=str[i]; str[i]=str[j]; str[j]=k; } }

5．下面程序中有一处错误，请指出，并改正。

main() {

float a[10]; int i;

for(i=0; i<3; i++) scnaf(”%d”,&a[i]); for(i=1; i<3; i++) a[0]=a[0]+a[i]; printf(”%f\\n”,a[0]); }

五、程序设计题

1．设计求二叉树深度的算法。

2．用递归方法，计算x的n次方。

3．如果一个正整数等于其各个数字的立方和，则该数称为阿姆斯特朗数。试编程求1000以内的所有阿姆斯特朗数。

(注:计算机组成原理部分去掉了,2003年含有数据结构,C语言和计算机组成原理)

2005年吉林省普通高校专升本教育试点考试

计算机科学与技术专业综合试卷

一、填空题

1．栈的主要特点是 ；队列的主要特点是 。 2．在一长度为n的向量中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动 个元素。

3．对于一个具有n个结点的单链表，在已知P所指结点后插入一个新的结点的时间复杂度为 ；在给定值为x的结点后插入一个新的结点的时间复杂度为 。

4．设n行n列的下三角矩阵A已压缩到一维数组s[0?n*(n-1)/2]中，若按行序为主存储，则A[i][j]对应的s中的存储位置为 。

5．将f=1+1/2+1/3+?1/n转化成递归函数，其递归出口是 ，递归体是 。

6．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 。

7．具有n个叶子结点的哈夫曼树中，其结点总数为 。

8．对一个满二叉树，m个树叶，n个结点，深度为h，则n= 。 9．判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用 算法。

10．在各种查找方法中，平均查找长度与结点个数无关的查找方法是 。 11．快速排序在最坏情况下的时间复杂度为 。 12．一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为 。

13．直接存取文件是用 方法组织的。 14．-18在内存中的补码形式是 。

15．若a=3, b=4, c=5, d=6, 则执行完如下表达式（a<（b=2））&& (c=d)后，a= ，b= ，c= ，d= 。

二、单项选择题

1．线性表的顺序存储结构是一种（ ）的存储结构；线性表的链式存储结构是一种（ ）的存储结构。

A．随机存取，顺序存取 B．顺序存取，随机存取 C．索引存取，散列存取 D．散列存取，随机存取 2．表达式a*(b+c)-d的中辍表达式为（ ）

A．a b c d + - * B．a b c + * d – C．a b c * + d - D．- + * a b c d 3．在一个单链表中，若P所指结点不是最后的结点，在P之后插入S所指结点，则执行（ ）

A．S->next=P; P->next=S; B．S->next=P->next; P->next=S; C．S->next=P->next; P=S; D．P->next=S; S->next=P;

4．一个栈的入栈序列为1，2，?，n，其输出序列为P1，P2，?，Pn，若P1=n，则Pi为（ ）

A．i B．n-i C．n-i+1 D．不确定

5．数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行序存放时，元素A[8][5]的起始地址为（ ）

A：n B：2n C：n-1 D：2n-1 5. int x,y; for(i=1,i

printf(“the one sent\\n”); }

运行成寻输出“the one sent”的行数（）

A：x*y B： (x-1)*y C：(x-1)*(y-1) D:x*(y-1) 6.二叉树中第K层，最多有（）个节点

A：2k B：2k-1 C：2k-1 D：2k+1

7.一个二叉树中，有n 个度为2的节点；该二叉树有（）个叶子节点； A：n+1 B：n-1 C：2n+1 D：2n-1

8.在树中，一个节点有三个兄弟节点，该节点的双亲节点的度为（） A：2 B：3 C：4 D：5

9.一个循环队列用数组A[m]存储，没有标记变量，则该队列最多能输入（）个元素

A：m-1 B：m C：m+1 D：2m 10.int a=2,b=5,在TurobC中a>b的输出值是（） A：ture B: false C：1 D：0

11.int a=0,b=20,c=30 ,m,n;执行(m=a++)&&(n=++b)后，n的值为（） A：0 B：20 C：21 D：30 12.在C语言中，调用数学函数，要引用的头文件（） A：stdio.h B：math.h C：graph.h D：stream.h 二、填空题（20*2=40）（注：共20个题，只记起9个）

1.一个n阶的三角矩阵中它的存储空间为 2.一个n个节点的的无向图，是连通图，至少有 条边 3.对图进行广度遍历：要求尽量按字母序列输出

a c e b d f .

4.一个有10个节点的完全二叉树，有 层

5.一个有n 个节点的二叉树，用二叉链表储存，有 个空指针域 6.向一个队列中以a,b,c,d依次入队，则出队的序列为 7.已知a[4]={1,2,3}，那么a[3]的值为 8.已知a[4]={1,2,3}，*p=a，那么*(p++)的值为 9.给定一待排序列{12,10,44,56,78,23},写出用冒泡排序法进行第一趟排序后的结果 三、判断题（5*2=10）

1.顺序表的存取结构为顺序存取

2.在一棵完全二叉树当中，所有节点的度都为2 3.忘了~~

4.在一个有向图的邻接表中，边表的节点数等于该图的弧数

5.在一个完全二叉树中，如果一个节点没有左子树，那么该节点就是叶子节点

四、数据结构应用题

1.已知一棵树如下图所示（7分）

R A B C D E F

（1）将该树转换成二叉树

（2）对该二叉树，按照左根序、中根序、后跟序，写出相应的遍历序列 2.给下列无向网图（10分）

A 12 2 8 C 6 9 3 B 10 D 7 E

（1）用邻接矩阵存储改图

（2）用Kruskal算法画出最小生成树，每一次只加一条边 3.散列表题。（10分）

散列函数的设计H(k)=k%7或（H(k)=k mod7）,以线性探测法处理冲突，存储下数据｛36，15，47，52，44｝

（1）请填写下表 0

（2）查找关键码44要比较几次？ 4.哈夫曼树题（10分） ｛4，5，6，7，18，10，12｝

（1）画出该哈夫曼树，要求左孩子的权值小于右孩子的权值 （2）求WPL值

5.定义一个单链表节点结构 struct node { };

struct node *p,*q;

已知指针*p和*q,p指向单链表中的一个节点，将q指向的节点插入到p节点的后面，写出语句序列。

int data; struct node *next;

1 2 3 4 5 6 五、程序填空题（每空2分，共30分）

1.补充以下程序，将x和y换值 void main() {

int x=5,y=3,temp; ; ; ; printf(“%d %d”,x,y); }

2.用插入排序对数组排序 int j;

for(int i=2;i

while(j>=0&&r[j]>r[0]) /* 找到插入位置 */ {

; j--; }

; /* 插入x */ }

3.以下程序功能是输入一个浮点型的数据，并输出，要求保留2位小数 void main() { float x; ; printf(“ ”,x); } 4.忘了~~ 5.忘了~~ 六、看程序写结果题

1. void main() { int i;

int a[6]={1,1}; for(i=2;i<6;i++) { }

for(i=0;i<6;i++) } 2. 忘了~~ 3. void main() { int i,j;

for(i=1;i<=3;i++) {

for(j=1;j<=i;j++) {

printf(“C”); printf(“\\n”) ; } } } 4.

#define PI 3 #include int area(int x,int y) {

int z= PI*x*y; printf(“%d”,z); }

printf(“%d ”,a[i]); a[i]=a[i-2]+a[i-1];

main() {

int a=4,b=5; area(a,b); } 5. main() {

int sage=70,s; s=sage/10; switch(s) { case 9: case 8: case 7:

case 6: pintf(“SUCCESS”); break;

default: printf(“FAILED”); } }

七、编程题（1*10=10）

1.在一个灰图形脱色的时候，以如图所示的RGB图形矩阵为例，编写一个程序，定义一个整型的二维数组，并在定义的时候将其初始化，用两个双For循环将矩阵中所有小于5的元素赋值为0，在用两个For双循环将修改后的二维矩阵按行序输出。 3649 1 4 800 2699 3 4

本文来源：https://www.bwwdw.com/article/dybd.html