数据结构（本）课程别末棕合练习(2008年12月6日) 中央电大工学院王春风 一、单项选择愿（每小愿2分） 1,针对线性表，在存储后如果最常用的慢作是取第1个结点及其前取，则采用() 存储方式最节省时何， A.单链表B。顺序表C,单循环链表D,双随表 2.替表所具备的特点是()。 A.可以随机访问任一结点 B.。占用连线的存储空间 C。可以通过下标对链表进行直接访问 D。插入副除元素的操作不需要移动元素结点 3.数据结构中，与所使用的计算机无关的是数据的()结构。 A。物理 B,存储 C,覆辑D,逻辑与物理 4.线性结构中数据元素的位置之间存在()的关系。 A。一对多 B.一对一 C.多对多 D。每一个元素都有一个直接前题和一个直接后推 5.以下特狂中，()不是算法的特性， A.有穷性 B.确定性 C.有0个或多个输出D.可行性 6,算法的时间复杂度与〔()有关。 A。所使用的计算机B.与计算机的操作系统 C,与数据结构 D,与算法本身 7.设有一个长度为的顺序表，要在第i个元素之前（也就是插入元素作为新表的第 1个元素)，则移动元素个数为《)。 A,一i+1 B.n-i C.-i-1 D.1 8。在一个单链表中，p、q分别指向表中两个相邻的结点，且口所指结点是p所指结点 的直接后继，现要刚除Q所指结点，可用的语句是()。 A.p=q->next B.p->next=g C.p->next=gnext D.q->next=NULL 9。候的插入到除操作在()进行： A栈底 B.栈顶 C.任意位置 D.指定位置
1 数据结构（本）课程期末综合练习（2008 年 12 月 6 日） 中央电大工学院 王春凤 一、单项选择题（每小题 2 分） 1．针对线性表，在存储后如果最常用的操作是取第 i 个结点及其前驱，则采用（ ） 存储方式最节省时间。 A．单链表 B．顺序表 C．单循环链表 D．双链表 2．链表所具备的特点是（ ）。 A．可以随机访问任一结点 B．占用连续的存储空间 C．可以通过下标对链表进行直接访问 D．插入删除元素的操作不需要移动元素结点 3．数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A．物理 B．存储 C．逻辑 D．逻辑与物理 4．线性结构中数据元素的位置之间存在（ ）的关系。 A．一对多 B．一对一 C．多对多 D．每一个元素都有一个直接前驱和一个直接后继 5．以下特征中，（ ）不是算法的特性。 A．有穷性 B．确定性 C．有 0 个或多个输出 D．可行性 6．算法的时间复杂度与（ ）有关。 A．所使用的计算机 B．与计算机的操作系统 C．与数据结构 D．与算法本身 7．设有一个长度为 n 的顺序表，要在第 i 个元素之前（也就是插入元素作为新表的第 i 个元素），则移动元素个数为（ ）。 A．n-i+1 B．n-i C．n-i-1 D．i 8．在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结点 的直接后继，现要删除 q 所指结点，可用的语句是（ ）。 A．p=q->next B．p->next=q C．p->next=q→next D．q->next=NULL 9．栈的插入删除操作在（ ）进行。 A．栈底 B．栈顶 C．任意位置 D．指定位置
10,在一个硅队中.假设t和r分别为队头和队尾指针，则副除一个结点的运算为()。 A.r=f->next:B.r=r->next:C.f=r->next:D.f=f->next: 1山.以下说法正确的是(). A,找的特点是先进先出，队列的特点是先进后出B,找和风列的特点都是先进后出 C。栈的特点是先进后出，队列的特点是先进先出D.栈和队列的特点都是先进先出 12.元素3,6,9按顺序依次进栈。则该栈的不可能输出序列是()（进栈出栈可 以交替进行). A.9,3,6 B.9,6.3 C,6.3,9 D,3,9,6 13。元素2,4,6,8按顺序依次进钱，则该栈的不可能输出序列是()（进栈出慢 可以交替进行) A,8.6,4,2 B.2,4.6,8 C.4,2,8,6 D.8,6,2,4 14.设有一个10阶的对称矩阵A,采用压锦存储的方式，将其下三角部分以行序为主 存储到一维数组B中（数组下标从1开始），则矩阵中元素A,在一维数组B中的下 标是(). A,33 B,32 C.85 D.41 15.设有一个15阶的对称更阵A,采用压馏存储的方式，将其下三角部分以行序为主 序存储到一维数组B中（数组下标从1开始），则矩阵中元素出：在一推数组B中 的下标是《). A.42 B.13 C.27 D.32 16.在C语言中，顺序存储长度为3的字符串，需要占用()个字节。 A.3 B.4 C,6 D,12 17.串函数StCp(“d”,“D)的值为(). A.0 B.1 C.-1 D.3 18。一棵有■个结点采用链式存储的二叉树中，共有《)个指针域为空。 A.n+l B.n C.n-l D.-2 19.在一裸二叉树中，若编号为1的结点存在右孩子，则右孩子的顺序编号为〔). A.2到 B.21-1 C.21+2 D.21+1 0.设一棵哈夫曼树共有个叶结点，则该树有()个非叶结点。 2
2 10．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（ ）。 A．r=f->next; B．r=r->next; C．f=r->next; D．f=f->next; 11．以下说法正确的是（ ）。 A．栈的特点是先进先出，队列的特点是先进后出 B．栈和队列的特点都是先进后出 C．栈的特点是先进后出，队列的特点是先进先出 D．栈和队列的特点都是先进先出 12．元素 3，6，9 按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可 以交替进行）。 A．9，3，6 B．9，6，3 C．6，3，9 D．3，9，6 13．元素 2，4，6，8 按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈 可以交替进行）。 A．8，6，4，2 B．2，4，6，8 C．4，2，8，6 D．8，6，2，4 14．设有一个 10 阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主 存储到一维数组 B 中（数组下标从 1 开始），则矩阵中元素 A8,5 在一维数组 B 中的下 标是（ ）。 A．33 B．32 C．85 D．41 15．设有一个 15 阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主 序存储到一维数组 B 中（数组下标从 1 开始），则矩阵中元素 a7,6 在一维数组 B 中 的下标是（ ）。 A．42 B．13 C．27 D．32 16．在 C 语言中，顺序存储长度为 3 的字符串，需要占用（ ）个字节。 A．3 B．4 C．6 D．12 17．串函数 StrCmp（“d”，“D”）的值为（ ）。 A．0 B．1 C．-1 D．3 18．一棵有 n 个结点采用链式存储的二叉树中，共有（ ）个指针域为空。 A．n+1 B．n C．n-1 D．n-2 19．在一棵二叉树中，若编号为 i 的结点存在右孩子，则右孩子的顺序编号为（ ）。 A．2i B．2i-1 C．2i+2 D．2i+1 20．设一棵哈夫曼树共有 n 个叶结点，则该树有（ ）个非叶结点
A.-1 B.n C.n+1 D.2n 21.设一棵有m个结点采用随式存储的二叉树，则该树共有()个指针域为空。 A,2如 B.n+1 C.2a+1 D.2-2 2.在一个无向图中，所有顶点的度数之和等于边数的()倍： L.3 B.2.5 C.1.5 D.2 马，己知如图1所示的一个图，若从项点。出发，按度优先瘦索法进行遍历，则可能 得到的一种顶点序列为《。 A.abcedf B.aebefd C.abcefd D.acfdeb 图1 24.已知如图1所示的一个图，若从顶点V,出发，按广度优先进行着历，则可伦得到 的一种顶点序列为《)。 A.ViV ViVeV:V VaV. B.VVVV.YeV.VV C.ViV:VVaVVeVVe D.ViV-VV.VVVeV
3 A．n-1 B．n C．n+1 D．2n 21．设一棵有 n 个结点采用链式存储的二叉树，则该树共有（ ）个指针域为空。 A．2n B．n+1 C．2n+1 D．2n+2 22．在一个无向图中，所有顶点的度数之和等于边数的（ ）倍。 A．3 B．2.5 C．1.5 D．2 23．已知如图 1 所示的一个图，若从顶点 a 出发，按广度优先搜索法进行遍历，则可能 得到的一种顶点序列为（ ）。 A．abcedf B．aebcfd C．abcefd D．acfdeb 图 1 24．已知如图 1 所示的一个图，若从顶点 V1 出发，按广度优先进行遍历，则可能得到 的一种顶点序列为（ ）。 A．V1V2V3V6V7V4V5V8 B．V1V2V3V4V5V8V6V7 C．V1V2V3V4V5V6V7V8 D．V1V2V3V4V8V5V6V7 b d f e c a V6 V7 V1 V2 V3 V8 V4 V5
图1 25.在有序表{1,3,813,33,42,46,6376,78,86,97,1000中，用折半查找 值85时，经()次比较后查找成功， A.3 B.4 C.6 D.8 25.在有序表2,4,7,14,34.43,47,64,75,80.90,97,120)中，用折半查找 法查找值80时，经《)次比较后查找成功， A,2 B.3 C,4 D.5 红.有一个长度为10的有序表，按折半直找对该表进行查找，在等概率情况下查找成 功的平均比较次数为() A.31/10 B.29/10 C.2s/10 D.29/9 8。排序算法中，从未排序序列中依次取出元素与己排序序列（初始为空）中的元素进 行比较《要求比较次数尽量少)，然后将其成入已排序序列的正确位置的方法是 () A,冒泡 B,直接插入C,选释排序 D,折半括入 29.一组记录的关健字序列为(37,70,47,29,31,85)，利用快速排序，以第一个 关键字为分制元素，经过一次划分后结果为《)。 A.29,31,37.,47,70,85 B.31,29,37,47,70,85 C.31.29,37,70,47,85 D.31.29,37,85,47,70 30.排序方法中，从尚未排序序列中挑透元素，并将其依次放入已排序序列（初始为空） 的一端的方法，称为()排序。 A。归并 B.插入 C,选择 D.快速 二、填空题（每小题2分） 1.把数据存储到计算机中，井具体体现数据之侧的 称为物理（存储）结构。 2,结构中的数据元素存在多对多的关系移为 结构。 3,结构中的数据元素存在一对一的关系移为 结构。 4.要求在个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较 的次数和算法的时间复条度分别为和0()： 5,在双向链表中，每个结点有两个指针域。一个指向结点的直接后继，另一个指向 6.设有一个头指针为h©ad的单向循环链表，p指向链表中的结点，若)ext一
4 图 1 25．在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找 值 86 时，经（ ）次比较后查找成功。 A．3 B．4 C．6 D．8 26．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120}中，用折半查找 法查找值 80 时，经（ ）次比较后查找成功。 A．2 B．3 C．4 D．5 27．有一个长度为 10 的有序表，按折半查找对该表进行查找，在等概率情况下查找成 功的平均比较次数为（ ）。 A．31/10 B．29/10 C．26/10 D．29/9 28．排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进 行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是 （ ）。 A．冒泡 B．直接插入 C．选择排序 D．折半插入 29．一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个 关键字为分割元素，经过一次划分后结果为（ ）。 A．29，31，37，47，70，85 B．31，29，37，47，70，85 C．31，29，37，70，47，85 D．31，29，37，85，47，70 30．排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空） 的一端的方法，称为（ ）排序。 A．归并 B．插入 C．选择 D．快速 二、填空题（每小题 2 分） 1．把数据存储到计算机中,并具体体现数据之间的 称为物理（存储）结构。 2．结构中的数据元素存在多对多的关系称为_____ ___结构。 3．结构中的数据元素存在一对一的关系称为________结构。 4．要求在 n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较 的次数和算法的时间复杂度分别为________和 O(n)。 5．在双向链表中，每个结点有两个指针域，一个指向结点的直接后继，另一个指向 ________ _。 6．设有一个头指针为 head 的单向循环链表，p 指向链表中的结点，若 p->next=
=则D所指结点为尾结点。 T,设有一个头指针为head的单向链表，p指向表中某一个结点。且有一>ert==山 通过操作 就可使该单向链表构造成单向循环链表。 8,肉一个找膜指针为的随栈中插入一个s所指结点时，可执行 和=8： 9,从一个栈项指针为h的链栈中刷除一个结点时，用x保存棱刷结点的值，可执行 和hh->next:。(结点的指针城为ext) 1D.在一个能队中，设「和r分别为队头和队尾指针，则插入s所指结点的操作为一 和=s:(结点的指针域为next) 1山，两个串相等的充分必要条件是 12.设有■阶对称阵A,用数组5进行压缩存储，当《灯时，A的数组元素，相应于 数组S的数如元素的下标为一·（数组元素的下标从！开始） 13,对二叉树的追历可分为 和层次四种不同 的遍历次序。 14.一裸二又树中顺序编号为的结点，若它存在左、右孩子，则左、右孩子编号分别 为 15.一保有■个叶结点的二叉树，其每一个丰叶结点的度数都为2，则该树共有 个结点。 16.一棵保有2一1个结点的二叉树，其每一个套叶结点的度数军为2，则该树共有 个叶结点。 17.一棵有14个结点的完全二叉树，则它的最高层上有一个结点。 18。赠历二叉样序树可得到一个有序序列： 19.如图2所示的二叉树，其先序薄历序列为
5 =_______，则 p 所指结点为尾结点。 7．设有一个头指针为 head 的单向链表，p 指向表中某一个结点，且有 p->next= =NULL, 通过操作________，就可使该单向链表构造成单向循环链表。 8．向一个栈顶指针为 h 的链栈中插入一个 s 所指结点时，可执行 和 h=s;。 9．从一个栈顶指针为 h 的链栈中删除一个结点时，用 x 保存被删结点的值，可执行 和 h=h->next;。(结点的指针域为 next) 10．在一个链队中，设f和 r分别为队头和队尾指针，则插入 s所指结点的操作为________ 和 r=s; (结点的指针域为 next) 11．两个串相等的充分必要条件是_______ ___。 12．设有 n 阶对称矩阵 A，用数组 S 进行压缩存储，当 i<j 时，A 的数组元素 aij 相应于 数组 S 的数组元素的下标为_______。（数组元素的下标从 1 开始） 13．对二叉树的遍历可分为___ _____、 、 和层次四种不同 的遍历次序。 14．一棵二叉树中顺序编号为 i 的结点，若它存在左、右孩子，则左、右孩子编号分别 为_____ _、___ _____。 15．一棵有 n 个叶结点的二叉树，其每一个非叶结点的度数都为 2，则该树共有_______ 个结点。 16．一棵有 2n-1 个结点的二叉树，其每一个非叶结点的度数都为 2，则该树共有_______ 个叶结点。 17．一棵有 14 个结点的完全二叉树，则它的最高层上有_______个结点。 18．________遍历二叉排序树可得到一个有序序列。 19．如图 2 所示的二叉树，其先序遍历序列为_____ ____。 e f g i b a c h d
图2 20.如图2所示的二又树，其前序海历序列为 1.哈希函数是记录关健字值与该记录存储地址之间所构造的 2,二叉树为二夏排序的充分必要条件是其任一结点的植均大于其左孩子的值、小于其 右孩子的值。这种说法是 的。《回答正确或不正确) 3.二义树排序中任一棵子树都是二义排序树。这种说法是 的。国答正确或不 正确) 图2 24.按某关键字对记录序列排序，着】 在排序前和排序后仍保持它们的 前后关系，则排序算法是稳定的，否则是不稳定的。 三、惊合题（每小题10分） 1,设一组记录的关键字序列为(49,83.59,41,43,47)，采用堆排序算法完成以下 操作：（要求小根堆，并画出中间过程） (1)以二叉树搭述6个元素的初始量 (2)以二义树描述逐次取走堆项元素后，经调整得到的5个元素、4个元素的堆 6
6 图 2 20．如图 2 所示的二叉树，其前序遍历序列为_______ __。 21．哈希函数是记录关键字值与该记录存储地址之间所构造的 。 22．二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其 右孩子的值。这种说法是__________的。(回答正确或不正确) 23．二叉树排序中任一棵子树都是二叉排序树，这种说法是_______的。(回答正确或不 正确) 图 2 24．按某关键字对记录序列排序，若 在排序前和排序后仍保持它们的 前后关系，则排序算法是稳定的，否则是不稳定的。 三、综合题（每小题 10 分） 1．设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下 操作：（要求小根堆，并画出中间过程） （1）以二叉树描述 6 个元素的初始堆 （2）以二叉树描述逐次取走堆顶元素后，经调整得到的 5 个元素、4 个元素的堆 g f a b d e c
2.一组记录的关键字序列为《6,79,56,38,0,84) (1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交 换元需的过程，要求以升序排列》 (2)对上述序列用堆排序的方法建立大根堆，要求以二叉树遥次描述建堆过程。 3.设有序表为(13,19.25,36,48.51,63,84,91,116,135,200)，元素的下 标依次为1,2，，12. (1)说出有哪儿个元素需要经过4次元素间的比较才能成功查到 (2)面出对上述有序表进行折半查找所对应的判定树《树结点用下标表示) (3)设查找元素5，需要进行多少次元素间的比较才能确定不能查到 4.设查找表为(18.15.20,53.64,7). (1》用冒泡法对该表进行排序（要求升序排列）。写出每一墙的推序过程，通常对个元 素进行冒泡排序要进行多少墙冒泡？第韬要进行多少次元素间的比较： 2)在排序后的有序表的基础上。画出对其进行折率查找所对应的判定树.（要求以数据 元素作为树结点) (③)求在等概率条件下，对上述有序表成功查找的平均查找长度， 5. (1)对给定数列7,16,4,8,20,9,6,18,5司，依次取数列中的数据，构造一棵二又排序树 (2》对一个给定的查找值，简述针对二义排序树进行查找的算法步露，在上述二义树中查 找元需20共要进行多少次元需的比较？ 8. (》“一樱二义树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值， 则该树一定是二叉排序树”。该说法是否正确，若认为正确。，则回答正确。若认为不正确则 说明理由？ (2)设有查找表7,16,4,820,9,6,18,5引，依次取表中数据构造一棵二叉排序树 对上述二夏树给出后序遍历的站果， 四、程序填空题（每空2分） 1.以下冒泡法程序对存放在a[1】,a[2],,a[]中的序列进行排序，完成程序中 的空格部分，其中m是元素个数，要求按升序排列。 void bsort (NODE a[]int n) NODE terp: 7
7 2．一组记录的关键字序列为（46，79，56，38，40，84） （1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交 换元素的过程，要求以升序排列） （2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 3．设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下 标依次为 1,2,……,12。 （1）说出有哪几个元素需要经过 4 次元素间的比较才能成功查到 （2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示） （3）设查找元素 5，需要进行多少次元素间的比较才能确定不能查到 4．设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对 n 个元 素进行冒泡排序要进行多少趟冒泡？第 j 趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据 元素作为树结点) (3)求在等概率条件下,对上述有序表成功查找的平均查找长度. 5． （1）对给定数列{7,16,4,8,20,9,6,18,5}，依次取数列中的数据，构造一棵二叉排序树。 (2 )对一个给定的查找值,简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查 找元素 20 共要进行多少次元素的比较? 6． (1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值， 则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则 说明理由？ (2)设有查找表{7，16，4，8，20，9，6，18，5}，依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果. 四、程序填空题（每空 2 分） 1．以下冒泡法程序对存放在 a[1]，a[2]，……，a[n]中的序列进行排序，完成程序中 的空格部分，其中 n 是元素个数，要求按升序排列。 void bsort (NODE a[ ], int n) { NODE temp;
int i,j,flag: for(j=1:(1) :++): (flag-0: for(1=1:(2】 :1++》 if(a[i].key>ai+l】.key】 (flag=1: temp-a[i]: (3) (4) if(flag"=0)break; 1 程序中f1ag的功能是(5】 2.以下是用头插法建立带头结点且有个结点的单向链表的程序，要求结点中的数据 域从前向后依次为n,-1,…,1,完成程序中空格部分。 E create2(n) (NC0 E *head,◆p.: int i: p-(NODE)malloc(sizeof(NODE)) p->next=NILL: head(l】 (2) for(i=1:idta=l日 if(i==1) p->next-NULL; else p->next=(4】
8 int i,j,flag; for(j=1; （1） ;j++); {flag=0; for(i=1; （2） ;i++) if(a[i].key>a[i+1].key) {flag=1; temp=a[i]; （3） ; （4） ; } if(flag= =0)break; } } 程序中 flag 的功能是（5） 2．以下是用头插法建立带头结点且有 n 个结点的单向链表的程序，要求结点中的数据 域从前向后依次为 n,n-1,……,1，完成程序中空格部分。 NODE *create2(n) {NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE)); p->next=NULL; head=（1） ; （2） ; for(i=1; idata=i; if(i= =1) p->next=NULL; else p->next= （4） ;
q->next=(5) return (head): 3.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左， 右指针城分别为1eft和rt,数据减ata为字符型，BT指向根结点)。 void Preorder (struct BTreeNode *BT) if(BT!-NULL)( 1) 2) (3) 4.以下程序是后序考历二叉树的递白算法的程序，完成程序中空格部分（树结构中， 左，右指针域分别为left和right,数据域dnta为字符型，BT指向根结点)， void Postorder (struet BTreeNode *8T) L1fBr=M》( 1) (2) (3) 9
9 q->next= （5） ; } return(head); } 3．以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点）。 void Preorder (struct BTreeNode *BT) { if(BT!=NULL){ （1） ; （2） ; （3） ; } } 4．以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中， 左、右指针域分别为 left 和 right，数据域 data 为字符型，BT 指向根结点）。 void Postorder (struct BTreeNode *BT) { if(BT!=NULL){ （1） ; （2） ; （3） ; } }
答案 一、单项选择题（每小题2分） 1.B2.D3.C4.B5.C6.D7.A8.C9.B10.D11.C12.A 13.D14.A15.C16.B17.B18.A19.D20.A21.B22.D23.C 24.C25.B26.C27.B28.D29.B30.C 二、填空题（每小题2分） 1.逻網结构 2.图状（网状） 3.线性 4.n-1 5,结点的直接前里 6.head 7.p->nextmhead; 8.s->next=h: 9.x=h-)data: 10.r->mext"s; 11.串长度相等且对应位置的字符相等 12.1(i-10/2+j 13.先序、中序、后序 14.21和21+1 15.2n-1 16.n 17.7 18.中序 19.abdgcefhi 20.abdefeg 21.对应关系 22.不正确 23.正确 24.关键字相等的记录
10 答案 一、单项选择题（每小题 2 分） 1．B 2．D 3．C 4．B 5．C 6．D 7．A 8．C 9．B 10．D 11．C 12．A 13．D 14．A 15．C 16．B 17．B 18．A 19．D 20．A 21.B 22．D 23．C 24．C 25．B 26．C 27．B 28．D 29．B 30．C 二、填空题（每小题 2 分） 1．逻辑结构 2．图状 （网状） 3．线性 4．n-1 5．结点的直接前驱 6．head 7．p->next=head; 8．s->next=h; 9．x=h->data; 10．r->next=s; 11．串长度相等且对应位置的字符相等 12．i(i-1)/2+j 13．先序、中序、后序 14．2i 和 2i+1 15．2n-1 16．n 17．7 18．中序 19．abdgcefhi 20．abdefcg 21．对应关系 22．不正确 23．正确 24．关键字相等的记录