数据结构试卷(98年上半年北京市)

日期:12-15| http://www.59wj.com |公共课历年真题|人气:437

数据结构试卷(98年上半年北京市)

  一、 单项选择题(在每小题的四个备选答案中选出一个正确的答案,并将其号码填在题干后的号码内,每小题2分,共10分)

  1.一个栈的输入序列为1,2,3,4,下面哪一个序列不可能是这个栈的输出序列?( )
  A. 1,3,2,4  B. 2,3,4,1   C. 4,3,1,2   D. 3,4,2,1

  2.下列排序方法中,哪一种方法的比较次数与纪录的初始排列状态无关?( )
  A. 直接插入排序   B. 起泡排序   C. 快速排序   D. 直接选择排序

  3.对n个记录的文件进行二路归并排序,总的时间代价为
  A. O(nlog2n)   B. O(n2)   C. O(log2n)   D. O(n)

  4.若一棵二叉树具有10个度为2的结点,则该二叉树的度为0的结点个数是( )
  A. 9  B. 11   C. 12  D. 不确定

  5.下面关于B树和B+树的叙述中,不正确的是
  A. B树和B+树都是平衡的多分树     B. B树和B+树都是可用于文件的索引结构
  C. B树和B+树都能有效地支持顺序检索  D. B树和B+树都能有效地支持随机检索

  二、 填空题(每空2分,共20分)

  1.从逻辑结构看,线性表是典型的 ,树是典型的 。

  2.设有二维数组A[0..9,0..19],其每个元素占两个字节,第一个元素的存储地址为100,若按行优先顺序存储,则元素A[6,6]的存储地址为 ,按列优顺序存储,元素A[6,6]的存储地址为 。

  3.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号,那么当i为 且小于n时,结点I的右兄弟是结点 ,否则结点i没有右兄弟。

  4.求具有最小带权外部路径长度的扩充二叉树的算法称为 算法。堆排序中建堆的方法称作 。

  5.6阶B树中,每个结点至多包含 个关键码,除根和叶结点外,每个结点至少包含 个关键码。

  三、 简答题(每小题6分,共18分)

  1.请简述散列函数在散列法存储中的作用,并举出一个散列函数的例子。

  2.请简述散列法存储中处理碰撞(冲突)的两类基本方法。

  3.请简述负载因子的定义,为什么说负载因子是散列法存储的一个重要参数?

  四、 求解下列问题(每小题6分,共30分)

  1.设待排序文件的关键码为(512,275,908,677,503,765,612,897,154,170)以第一元素为分界元素进行快速排序(按关键码值递增顺序),请给出一趟扫描后的结果。

  2.请画出下面的树所对应的二叉树。

  3.从一棵空的二叉排序树开始,将以下关键码值依次插入:25,13,15,31,7,20,37,请画出插入全部完成后的二叉排序树。

  4.请画出下面带权图的一棵最小生成树。

  5.对于下面的稀疏矩阵

  1)画出其三元组法存储表示。
  2)画出其行—列法(十字链表法)存储表示。
         
  五、 算法题(6分)
  有一个链接方式存储的线性表,表中每个结点包括两个指针,其结点用PASCAL语言描述如下:
  TYPE pointer=↑node;
  node=RECORD
  info:datatype;
  link1,link2:pointer
  END;
  其中link1是指向结点的下一个结点的指针,link2是指向结点的前一个结点的指针,如图所示。
      
  p和q都是pointer类型的变量,现要将q所指的新结点插入表中p所指结点的前面(说明:p所指的不是链表的第一个结点)。请用PASCAL语句写出该插入的关键步骤。(部要求写完整的算法,只要求用几个语句写出关键步骤。)
  
  六、 算法填空和分析(共16分)
  下面是用PASCAL语言编写的二分值插入排序算法,该算法对排序码为整数的线性表进行升序排序。
  TYPE node=RECORD
  key:integer;
  info:datatype
  End;
  list=ARRAY[1..max] OF node;
  PROCEDURE binarysort (VAR R: list; n: integer);
  VAR temp :node ;
  low,m,high,I,j: integer;
  BEGIN
nteger;
  BEGIN
nteger;
  BEGIN
nteger;
  BEGIN
  FOR I:=2 TO n DO
  BEGIN
  temp := R[ i ];
  low :=1; high := i-1;
  WHILE ① DO
  BEGIN
  m :=(low+high) DIV 2;
  IF ②
  THEN high :=m-1
  ELSE ③
  END;
  FOR j := i-1 DOWNTO ④ DO
  R[j+1] := R[j];
  ⑤
  END;
  END;

  1.请将算法的空缺处应填入的正确内容写在下面。(10分)
  ①
  ②
  ③
  ④
  ⑤

  2.设待排序的记录数n=7,当排序码的初始排列顺序分别为(15,25,35,45,55,65,75)和(75,65,55,45,35,25,15)时,请说出排序过程中对排序码所进行的总的比较次数分别是多少?(假定算法中取中项的整数除法采用小数截断的方法。)(6分)

www.59wj.com 如果觉得《数据结构试卷(98年上半年北京市)》公共课历年真题,zikao不错,可以推荐给好友哦。
本文Tags: 自学考试 - 历年真题 - 公共课历年真题,zikao,
在百度中搜索相关文章:数据结构试卷(98年上半年北京市)
在谷歌中搜索相关文章:数据结构试卷(98年上半年北京市)
在soso中搜索相关文章:数据结构试卷(98年上半年北京市)
在搜狗中搜索相关文章:数据结构试卷(98年上半年北京市)
相关分类导航|
热门推荐|