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

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<stdio.h>
int x=1;
main()
{
  func(x);
  printf(“%d\n”,x);
}
func(int x)
{
  x=3;
}
程序的执行结果是：
2．程序：
#include<stdio.h>
main()
{
  int a=2,*p,**pp;
  pp=&p;
  p=&a;
  printf(“%d,%d,%d”,a,*p,**pp);
}
程序的执行结果是：
3．程序：
#include<stdio.h>
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= =’ ‘)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。