当前位置：文档之家 › 04数据结构A

04数据结构A

  • 格式：doc
  • 大小：40.50 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

数据结构 试题(A)-答案

数据结构 试题(A)-答案
评分标准：有向图、无向图两种存储方式各占4分。
3.建立平衡二叉树过程如图2所示(图中加阴影的结点表示要调整的结点)。
图2构造平衡二叉树过程
评分标准：每次调整占1分。
4.答：不能。因为在这里，二分查找只减少了关键字间的比较次数，而记录的移动次数不变，时间的复杂度仍为O(n2)。
评分标准：答对“不能”占3分，说明理由占5分。
A.872B.860
C.868D.864
8.一个具有1025个结点的二叉树的高h为。
A.11B.10
C.11～1025D.12～1024
9.一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则先序遍历序列为。
A.ACBEDB.DECAB
C.DEABCD.CEDBA
10.对图1所示的无向图，从顶点1开始进行深度优先遍历；可得到顶点访问序列。
2.给出如下各种情况下求任意一个顶点的度的过程（只需文字描述）：（8分）
（1）含n个顶点的无向图采用邻接矩阵存储；
（2）含n个顶点的无向图采用邻接表存储；
（3）含n个顶点的有向图采用邻接矩阵存储；
（4）含n个顶点的有向图采用邻接表存储。
3.将整数序列{4,5,7,2,1,3,6}中的数依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树。（要求画出每个元素插入过程，若需调整，还需给出调整后的结果，并指出是什么类型的调整，12分）
A.输出第i(1≤i≤n)个元素值
B.交换第1个元素与第2个元素的值
C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
4.设n个元素进栈序列是p1，p2，p3，…，pn，其输出序列是1，2，3，…，n，若p3=3，则p1的值。
A.可能是2B.一定是2

南方学院2010-2011-1数据结构a

南方学院2010-2011-1数据结构a

南京林业大学南方学院试卷课程 数据结构(A 卷) 2010~2011学年第一学期注意：请将正确答案写在答题纸上，答在试卷上不给分。

一．是非题：（判断下列各题是否正确，正确的在括号内打 “√”，错的打“×”。

每小题2分，共20分）1. 数据的逻辑结构独立于计算机，物理结构依赖于计算机。

2. 算法和程序没有区别，所以在数据结构中两者是通用的。

3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

4. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。

5. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

6. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

7. 线性表可以看成是广义表的特例，若广义表中的每个元素都是原子，则广义表便成为线性表。

8. 用一维数组存储二叉树时，总是以先序遍历存储结点。

9. 用邻接矩阵存储一个图所需的存储单元数目与图的边数有关。

10. 二叉排序树的查找和折半查找的时间性能相同。

二．选择题（本大题共10小题，每小题2分，共20分）1．被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。

通常将数据元素之间的这种联系称为______。

A. 规则B. 集合C. 结构D. 运算2．算法的时间复杂度取决于______。

A．问题的规模B．待处理数据的初态C．A与B都对D．算法的易读性3．对于顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

删除一个元素时所需移动元素次数的期望值为______。

A. n/2B. (n+1)/2C. (n-1)/2D. n4．循环队列用A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，那么当前队列中的元素个数是______。

A．(rear-front+m)%m B．rear-front+1 C．rear-front-1 D．rear-front5．一个非空广义表的表头______。

VF试题及答案

VF试题及答案

VF试题及答案（一）一、选择题下列各题A) 、B) 、C) 、D) 四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上，答在试卷上不得分。

(1) DBMS的含义是：A) 数据库系统 B) 数据库管理系统C) 数据库管理员 D) 数据库(2)从关系模式中指定若干个属性组成新的关系的运算称为：A) 联接 B) 投影 C) 选择 D) 排序(3)对于“关系”的描述，正确的是：A) 同一个关系中允许有完全相同的元组B) 同一个关系中元组必须按关键字升序存放C) 在一个关系中必须将关键字作为该关系的第一个属性D) 同一个关系中不能出现相同的属性名(4)在表设计器的“字段”选项卡中可以创建的索引是A) 唯一索引 B) 候选索引 C) 主索引 D) 普通索引(5)在程序中不需要用public等命令明确声明和建立，刻直接使用的内存变量是A) 局部变量 B) 公共变量 C) 私有变量 D) 全局变量(6)扩展名为dbf的文件是A) 表文件 B) 表单文件 C) 数据库文件 D) 项目文件(7)下列程序段的输出结果是CLEARSTORE 10 TO ASTORE 20 TO BSET UDFPARMS TO REFERENCEDO SWAP WITH A,(B)A,BPROCEDURE SWAPPARAMETERS X1, X2TEMP=X1X1=X2X2=TEMPENDPROCA) 10 20 B) 20 20 C) 20 10 D) 10 10(8)使用调试器调试第(7)小题的程序，如果想在过程SWAP执行时观察X1的值，可以在其中安置一条命令，程序执行到该命令时，系统将计算X1的值，并将结果在调试输出窗口中显示，这条命令的正确写法是：A) DEBUGOUT X1 B) DEBUG X1 C) OUT X1 D) TEST X1(9) 设X=10, 语句?VARTYPE ("X")的输出结果是A) N B) C C) 10 D) X(10) 表达式LEN(SPACE(0))的运算结果是A) .NULL. B) 1 C) 0 D) ""(11) 为表单建立了快捷菜单mymenu，调用快捷菜单的命令代码DO mymenu.mpr WITH THIS 应该放在表单的那个事件中？A) Destory事件B) Init事件C) Load事件D) RightClick事件(12)(24)题使用的数据表如下：当前盘当前目录下有数据库：学院.dbc，其中有“教师”表和“学院”表。

数据结构试卷(A)答案

数据结构试卷(A)答案

运算机系2010年—2011年第一学期期末考试题（卷）《数据结构》试题A（卷）参考答案和评分标准一、选择题（每题2分，共40分）。

1.线性表假设采纳链式存储结构时，要求内存中可用存储单元的地址（D ）A．必需是持续的B．部分地址必须是连续的C．必然是不持续的D．连续不连续都可以2. 链表不具有的特点是（ C ）A．随机访问B．不必事先估计存储空间C．插入删除时不需移动元素D．所需空间与线性表成正比3.设有编号为1，2，3，4的4辆车，顺序进入一个栈结构的站台，以下不可能的出站顺序为（ D ）A．1234 B．1243 C．1324D．14234.顺序栈存储空间的实现利用（B ）存储栈元素。

A．链表B．数组C．循环链表D．变量5.初始化一个空间大小为5的顺序栈S 后，S->top的值是（ B ）A．0 B．-1 C．再也不改变D．动态变化6.队列是限定在（ D ）进行操作的线性表。

A．中间B．队首C．队尾D．两端7.引发循环队列队头位置发生转变的操作是（A ）。

A．出队B．入队C．取队头元素D．取队尾元素8.以下论述正确的选项是（C ）A．空串与空格串是相同的B．”tel”是”Teleptone”的子串C．空串是零个字符的串D．空串的长度等于19.串的模式匹配是指（D ）A．判定两个串是不是相等B．对两个串比较大小C．找某字符在主串中第一次显现的位置D．找某子串在主串中第一次显现的第一个字符位置=”morning”，执行求子串函数SubStr(S,2,2)后的结果为（ B ）A．”mo”B．”or”C．”in”D．”ng”11.设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包括的结点数至少为（ B ）A．2h B．2h-1 C．2h+1 D．h+112.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ D ）A．acbed B．decabC．deabc D．cedba13. 按照二叉树的定义，具有3个结点的二叉树有（ C ）种。

数据结构复习题1

数据结构复习题1
}
数据结构复习题2
一、选择题(30分)
1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)
2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。
(A) 2k-1(B) 2k(C) 2k-1(D) 2k-1
5.设哈夫曼树中共有n个结点，则该哈夫曼树中有___0_____个度数为1的结点。
6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。
7.__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。
8.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;
bitree *q[20]; int r=0,f=0,flag=0;
void preorder(bitree *bt, char x)
{
if (bt!=0 && flag==0)
int hashsqsearch(struct record hashtable[ ],int k)
{
int i,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}
(C)判别栈元素的类型(D)对栈不作任何判别

数据结构试卷A卷(含答案)

数据结构试卷A卷(含答案)
《数据结构》试卷A
一、填空题（每空1分，共22分） 1、数据结构被形式地定义为（D, R），其中D是
的有限集合，R是
D上的 有限集合。 2、一个算法的效率可分为 效率和 效率。 3、向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时， 需向后移动 ________个元素。 4、在一个循环队列中，队首指针指向队首元素的 位置。 5、在具有n个单元的循环队列中，队满时共有 个元素。 6、向栈中压入元素的操作是先 ，后 。 7、 称为空串； 称为空白串。 8、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字 节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积 （存储量）为 ；末尾元素A57的第一个字节地址为 ；若按行 存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47 的第一个字节地址为 。 9、设一棵完全二叉树具有1000个结点，则此完全二叉树有 个 叶子结点，有 个度为2的结点，有 个结点只有非空左子树， 有 个结点只有非空右子树。 10、线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给 定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下， 最多需要检索 次。设有100个结点，用二分法查找时，最大比较次数 是 。 11、散列法存储的基本思想是由 决定数据的存储地址。
6.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分 别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个 字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。 对于上述实例，比较两种方案的优缺点。
五、算法设计（在下列算法的横线内填上适当的语句或表达式。） 1、直接选择排序 void selectsort (int R[ ] ) // 按递增序对R[ 0 ] ~R[n-1] 进行直接选择排序 { int i, j, k, temp ; for (i=0; i<= ; i++) { k=i ; for (j= ; j<=n-1; j++) if (R[ j ] R[ k ] ) k=j; if （ ） { temp=R[ i ]; R[ i ] = ; R[ k ]=temp; } } } 2、中序遍历二叉树 设二叉树用二叉链表表示，以t为根指针，二叉链表结点的类型为 node；栈s的元素类型为指向node的指针类型, 栈容量m足够大。中序遍 历的非递归算法如下： struct node {char data; node *lc,*rc; }; void preorder (node *t) { node *s[m] ，*p=t ; int top =- 1； do { while (p!=NULL) { s[++top] = } if (top!= -１) ｛p=s[top- -]；

数据结构试题A答案

数据结构试题A答案陕西科技⼤学试题纸（A参考答案及评分标准）课程数据结构班级信息、数学05学号姓名请在每⼩题的四个备选答案中，选出⼀个正确的答案，并将其号码填在括号内。

1.设⼀个栈的输⼊序列为1，2，3，4，则借助⼀个栈所得的输出序列不可能是（D）。

A．1，2，3，4 B．4，3，2，1C．1，3，4，2 D．4，1，2，32. 设有80⾏的⼆维数组A[80][60]，其元素长度为4字节，按⾏优先顺序存储，基地址为300，则元素A[18][25]的存储地址为（D）。

A．3800 B．4376 C．3900 D．47203. 将⼀棵有100个节点的完全⼆叉树从根这⼀层开始，每⼀层上从左到右依次对结点进⾏编号，根节点的编号为0，则编号为49的结点的左孩⼦编号为（B）。

A．98 B．99 C．50 D．494. 在长度为n的顺序存储的线性表中，删除第i个元素（1≤i ≤n）时，需要从前向后依次前移（A）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i5. 栈的插⼊和删除操作在（A）进⾏。

A．栈顶B．栈底C．任意位置D．指定位置6. 链表适⽤于（A）查找。

A．顺序B．⼆分法C．⼆分法、顺序D．随机7. 深度为6(根结点的层次为1)的⼆叉树⾄多有（D）个结点。

A．64 B．32 C．31 D．638. ⽤邻接表表⽰图进⾏⼴度优先遍历时，通常是采⽤（B）来实现算法的。

A．栈B．队列C．树D．图9. 设有两个串ｐ和ｑ，求ｑ在ｐ中⾸次出现的位置的运算称作（B）。

A．连接B．模式匹配C．求⼦串D．求串长10.若某线性表中最常⽤的操作是取第i个数据元素，则采⽤（D）存储⽅式最节省时间。

A．单链表B．双链表C．单向循环D．顺序表11.三个结点可构成（D）个不同形态的⼆叉树。

A．2 B．3 C．4 D．512.下列关键字序列中，（D）是堆。

A．16,72,31,23,94,53 B．94,23,31,72,16,53C．16,53,23,94,31,72 D．16,23,53,31,94,7213.把⼀棵树转换为⼆叉树后，这棵⼆叉树的形态是（A）。

数据结构试卷带答案

数据结构试卷（一)一、选择题(20分）1．组成数据的基本单位是（ 1.C ）。

(A）数据项（B）数据类型（C) 数据元素(D）数据变量2．设数据结构A=(D,R），其中D=｛1，2，3,4｝，R={r｝，r=｛〈1，2〉,<2，3>，〈3,4>,〈4，1〉｝，则数据结构A是（ C ）.(A）线性结构（B）树型结构 (C）图型结构(D）集合3．数组的逻辑结构不同于下列（D）的逻辑结构.（A）线性表（B）栈(C) 队列(D）树4．二叉树中第i（i≥1）层上的结点数最多有（C）个。

(A） 2i （B) 2i(C） 2i—1（D） 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）.（A) p-〉next=p—>next—〉next （B) p=p—〉next(C）p=p-〉next-〉next (D）p—〉next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是(。

C ).（A） 6 （B) 4 (C） 3 (D） 27．将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为(C ).(A） 100 （B） 40 (C） 55 (D） 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8。

B（A） 3 (B） 4 (C) 5 （D） 19．根据二叉树的定义可知二叉树共有（ B)种不同的形态。

（A） 4 (B) 5 （C) 6 （D) 710.设有以下四种排序方法，则（ B ）的空间复杂度最大.（A）冒泡排序（B) 快速排序（C）堆排序(D) 希尔排序二、填空题（30分)1.设顺序循环队列Q［0：m-1］的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置,队尾指针R指向当前队尾元素所在的位置，则出队列的语句为 F =____________;.2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。

03教育《数据结构》试题(a)

密封线滨州学院2004—2005学年第一学期期末考试03教育《数据结构》试题（A ）一、单项选择题(在每个小题的四个备选答案中，只有一个答案是正确的，请将正确答案的号码填在题干后的括号内。

每空2分，共30分) 1.一个栈的入栈顺序是ABCDE ，则不可能的出栈顺序是（）A .EDCBA B. DECBA C .DCEAB D. ABCDE 2..在线索二叉树上，线索是什么？ （ ）A 两个标志域B 指向结点前驱和后继的指针C 数据域D 指向左、右子树的指针3.在n 个结点的完全二叉树中，对任一结点I(1<=I<=N)，那么I 的左孩子可能是哪一个？ （ ）A. [I/2]B.2I+1C. 2ID.都不是4.已给如图所示哈夫曼树，那么电文CDAA 的编码是什么？ （ ） A.110100 B.11011100○C.010110111D.11111100 A ○B ○C D5.已给如图所示二叉树，a,b,c,d 分别带权值为7，5，2，4，则该树的带权路径长度是多少？（ ）○A.46B.36C.35D.都不是 ○ ○a b c d6.在图的表示中，哪一种是一种顺序表示法？（ ）A.数组B.邻接表C.十字链表D.邻接多重表7.将一株有100个结点的完全二元树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ ）。

A ．98B ．99C ．50D ．没有右孩子8.平衡二叉树上结点的平衡因子不能是哪一个值？ （ ） A.-1 B.0 C.1 D.29.堆排序在最坏情况下，其时间复杂度是多少？ （ ）A.O(2n) B.O(nlogn) C.O(n) D.都不是10．数据在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ ）。

A ．逻辑结构B ．顺序存储结构C ．链式存储结构D ．以上都对11. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8 12． 有关二叉树下列说法正确的是（ ）A ．二叉树的度为2B ．一棵二叉树的度可以小于2C ．二叉树中至少有一个结点的度为2D ．二叉树中任何一个结点的度都为213. 下面关于求关键路径的说法不正确的是（ ）。

数据结构智慧树知到课后章节答案2023年下黑龙江工程学院

数据结构智慧树知到课后章节答案2023年下黑龙江工程学院黑龙江工程学院绪论单元测试1.（）在其著作《计算机程序设计艺术》中，开创了数据结构的最初体系。

( )A:尼古拉斯·沃斯 B:理查德·卡普 C:史蒂芬·古克D:唐纳德·克努特答案:唐纳德·克努特2.（）提出了著名的公式程序=算法+数据结构。

( )A:尼古拉斯·沃斯 B:史蒂芬·古克C:唐纳德·克努特 D:理查德·卡普答案:尼古拉斯·沃斯3.数据结构课程不是（）课程的先修课程。

A:高级语言程序设计 B:计算机组成原理C:操作系统 D:数据库原理答案:高级语言程序设计4.下面哪个不是常见的数据结构。

（）A:线性方程组 B:树 C:线性表 D:栈答案:线性方程组5.下面说法错误的是（）。

A:我国高校从20世纪50年代就开设了数据结构这一课程B:精心选择的数据结构能够带来更高的计算速度和存储效率C:程序是为处理计算机问题编制的一组指令集D:通过数据结构课程，能够掌握数据结构的逻辑结构、存储结构及实现算法答案:我国高校从20世纪50年代就开设了数据结构这一课程第一章测试1.（）是组成数据具有独立含义不可分割的最小单位。

( )A:数据对象 B:数据项C:数据元素D:数据变量答案:数据项2.数据逻辑结构中非线性结构包括（）。

A:树形结构和图形结构B:图形结构和堆栈结构C:顺序结构和链式结构 D:树形结构和队列结构答案:树形结构和图形结构3.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={＜01，02＞，＜01，03＞，＜01，04＞，＜02，05＞，＜02，06＞，＜03，07＞，＜03，08＞，＜03，09＞}，则数据结构A是（）。

A:物理结构 B:图形结构C:树形结构 D:线性结构答案:树形结构4.数据结构的主要研究内容包括数据的（）以及数据的运算和操作。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
3）（3分）画出该图邻接表存储结构示意图。
4）（3分）画出对应无向图的最小生成树，给出生成树边权之和。(如果去掉方向后,一对顶点之间有两条以上的边,只保留权值最小的边)
2．已知关键字的集合{56，8，15，80，10，22，28，50，60,40,90}
（1）（3分）试按给出的序列构造一棵平衡二叉树。
3.对关键字码集合K={53，30，37，12，45，24，96}，从空二叉树出发建立与集合K对应的二叉排序树，若希望得到树的高度最小，应选择下列哪个输入序列。
A)45，24，53，12，37，96，30 B)12，24，30，37，45，53，96
C)37，24，12，30，53，45，96 D)30，24，12，37，45，96，53
13．在有n个结点的二叉链表中,值为空链域的个数为
A)n-1 B)2n-1 C)n+1 D)2n+1
14．具有1080个结点的完全二叉树的深度为
A) 12 B)10 C)11 D)13
15．若已知一个栈的入栈序列是元素1，2，3，....，n，其输出序列为p1,p2,p3,…pn,若p1是n，则pi是( )
A) i B)n-i C)n-i+1 D)不确定
16．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是
A) n B)(n-1)2C)n-1 D)n2
17．对线性表进行二分查找时，要求线性表必须
A)以顺序方式存储B)以链接方式存储
C)以顺序方式存储，且数据有序D)以链接方式存储，且数据有序
(1) A)6 B)5 C)4 D)3
(2) A)4 B)3 C)2 D)1
11．已知四个元素a,b,c,d依次进栈，进栈过程中可出栈，下面那一种出栈顺序是不正确的
A)a,d,c,b B)b,c,d,a C)c,a,d,b D)c,d,b,a
12．队列操作的原则是。
A)先进先出B)后进先出C)只能进行插入D)只能进行删除
b.在p结点前插入s结点的语句序列是(2)；
c.在表首插入s结点的语句序列是(3)；
d.在表尾插入s结点的语句序列是(4)；
(1) p->next=s;
(2) p->next=p->next->next;
(3) p->next=s->next;
(4) h=s;
(5) p=h;
(6) s->next=NULL;
8．一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号，则编号最小的叶子的序号是(14)；编号是i的结点所在的层次号是(15)（根所在的层次号规定为1层）。
三、简答题（35分）
1．已知有向图的带权矩阵为：
1)（3分）画出该有向图。
2) (3分)按Dijkstra算法,给出从顶点1(顶点标号从1计)到其余顶点的最短路径长度以及经过的中间点。
8.数组A的每个元素需要4个字节存放，数组有8行10列，若数组以行为主顺序存放在内存SA开始的存储区中，则A中8行5列的元素的位置是
A) SA+74 B)SA+292C)SA+296D)SA+300
9-10．在一棵7阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有(1)个关键字；若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是(2)。
18．若用起泡排序对序列{14,26,29,41,52,5}从小到大排序,需要次比较
A)15 B) 28 C)3 D)21
19．有一个有序表为{1，3，9，12，32，41，45，62，70，77，82，95，100}，当二分查找值62的数据时要次比较成功。
A)1 B) 2 C) 4 D) 3
20．设双向循环链表中结点的结构为（data,pre,next）。若在指针p所指结点之后插入结点s，则应执行下列操作
/ | \ / \ / | \
D E F L M R S T
4．（4分）按大顶堆将序列{56，8，15，80，10，22，28，50，60,40,90}调整为堆，写出最后的数据序列
5．（4分）给出拓扑排序算法描述（不用写C/C++算法）
四、算法设计（用类-C/类-C++描述）（16分）
1．(8分)完成一个二叉树左右子树交换的递归算法。
2．(8分)设在一个带头结点的双向链表中，所有结点的数据元素按值递增顺序排列，写一算法，删除表中所有大于min，小于max的元素（若存在）。双链表的定义如下：
typedef struct DLnode{
int data;
DLnode *pre, *next;
}DLnode;
A)p->next=s; s->pre=p; p->next->pre=s; s->next=p->next;
B)p->next=s; p->next->pre=s; s->pre=p; s->next=p->next;
C)s->pre=p; s->next=p->next; p->next=s; p->next->pre=s;
D)s->pre=p; s->next =p->next; p->next->pre=s; p->next=s;
二、填空题（19分,其余每空1分）
1．已知h是无表头结点的单链表，且p结点既不是首元结点，亦不是尾元结点，试从下列提供答案中选择合适的语句序列(给出序号)：
a.在p结点后插入s结点的语句序列是(1)；
A) 55 B)68 C)59 D)28
2.无向图G=（V，E），其中：V={ a,b,c,d,e,f} , E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行广度优先遍历，得到的顶点序列正确的是
A) a,b,e,c,d,f B) a,c,f,e,b,d C) a,e,b,c,f,d D) a,e,d,f,c,b
A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性
C)确定性、有穷性和稳定性D)易读性、稳定性和安全性
6．设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
A) 8 B) 3 C)2 D)9
4.已知一组数{20，8，6，2，30，1}的排序过程为：
（1）20，8，6，2，30，1
（2）1，8，6，2，30，20
（3）1，2，6，8，30，20
（4）1，2，6，8，20，30
问它是下面那一种排序：
A)快速排序B)直接插入排序C)起泡排序D)选择排序
5．计算机算法必须具备输入、输出和等五个特征。
(7)。
4．深度为k的完全二叉树至少有(8)个结点；至多有(9)结点。
5．在一棵二叉树中，度为1的结点有40个，总的结点数为99，则二叉树中叶子结点数共有(10)。
6．在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有
(11)个关键字；右边结点的关键字数是(12)。
7.求图的最小生成树有两种算法，(13)算法适合于求稀疏图的最小生成树。
7．在一个单链表中，若要删除p所指结点的后继结点，则执行。
A) p=p->next; p->next=p->next->next
B) free(p->next) (C语言格式)或delete p->next (C++语言格式)
C) p=p->next->next;
D) p->next=p->next->next
（2）（3分）试构造3阶B_树。
（3）（3分）写出依次删除关键字60,40后的B_树。
（4）（3分）按以上数据,用链地址法处理冲突(Hash函数H（key）=key % 13)，画出示意图(不要写算法)
3．（3分）已知三棵树的森林如下，试把它转化为二叉树
A G N
/ \ / | \ /\
B C H I K O P
(7) q=p;
(8) while(p->next!=NULL)p=p->next;
(9) while(p->next!=q )p=p->next;
(10) p=q;
(11) p=h; s->next=h;
(12) h=p;
(13) s->next=p->next;
2．图的遍历分为(5)和(6)。
3．假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，则先序序列为：
南京理工大学课程考试试卷（学生考试用）
课程名称：数据结构学分：3大纲编号
试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟
组卷日期：2006年5月18日组卷教师（签生姓名：
一、选择题（1.5*20=30分）
1.若以{4，5，6，3，8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是