国家开放大学《数据结构（本）》综合练习题参考答案

1、国家开放大学数据结构（本）综合练习题参考答案一、填空题1.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有（10）列。2.结构中的数据元素存在多对多的关系称为（图状）结构。3.在单向链表中，q指向p所指结点的直接后继结点，要删除q所指结点，可以用操作（p->next;）= q->next;。4.n个元素进行冒泡法排序，第j趟冒泡要进行（n-j）次元素间的比较。5.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和（数组元素）三项信息。6.中序遍历（二叉排序树）树可得到一个有序序

2、列。7.队列的操作特点是后进（后出）。8.待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后，结果序列为（1，2，4，8，3，5，9）。9.n个元素进行冒泡法排序，通常需要进行（n-1）趟冒泡。10.广义表（a，b），d，e（i，j），k）的长度是（4） 。11.中序遍历二叉排序树可得到一个（有序）的序列。12.广义表的（c，a，（a，b），d，e，（i，j），k）深度是（3）。13.广义表（c，a，（a，b），d，e，（i，j），k）的长度是（6）。14.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10 行10列的稀疏矩阵A共有95个零元素，其相应的三元组表

3、共有（5）个元素。15.广义表的（c，a，（a，b），d，e，（i，j），k）深度是（3）。16.在对一组记录（50，49，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65 插入到有序表时，为寻找插入位置需比较（3）次。17.循环队列在规定少用一个存储空间的情况下，队空的判定条件为（front=rear）。18.一棵有5个叶结点的哈夫曼树，该树中总共有（9）个结点。19.c语言中，字符串“E”存储时占（2）个字节。20.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有（12）个结点。（根所在结点为第1层）。21.一棵二叉树中有n个非叶结点，每一个非叶结

4、点的度数都为2，则该树共有（n+1）个叶结点。22.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为（32）。23.在对一组记录（55，39，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较（3）次。24.有以下程序段： char a =“English”; char *p=a; int n=0; while( *p!=0) n+; p+;结果中，n的值是（7）。25.设：char a ="AEIJING"该字符串在计算机中存储时占（8）个字节。栈的特点之一是：元素进、出栈的次序是：先进（后出

5、）。26.结构中的数据元素存在多对多的关系称为（图状）结构。27.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是（行下标，行下标，数组元素）。28.对稀疏矩阵进行压缩存储，可采用三元组表，一个有8行的稀疏矩阵A共有92个零元素，其相应的三元组表共有4个元素。该矩阵A有（12） 列。29.在对10个记录的序列（9，35，19，77，2，10，53，45，27，68）进行直接插入排序时，当把第6个记录10 插入到有序表时，为寻找插入位置，元素间需比较（4）次。（按升序排序）30.循环链队列中，设front和rear分别为队头和队尾指针，最大存储空间元素为MaxSize

6、，采用少用一个存储空间的模式，则判断循环链队列为空的条件是（front=rear）为真。31.字符串a1="beijing"，a2 ="bef"，a3="beifang"，a4="befi"最小的是（a2）。32.n个元素进行冒泡法排序，第j趟冒泡要进行（n-j）次元素间的比较。33.10个元素进行冒泡法排序，其中第5趟冒泡共需要进行（5）次元素间的比较。34.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有（12）个结点。（根所在结点为第1层）35.（中序）遍历一棵二叉排序树可得到一个有序序列。36中序

7、遍历一棵（二叉排序树）可得到一个有序序列。37.广义表（c，（a，b，c），（d，e，f），（i，j），k）的长度是（4）。38.待排序的序列为9，4，5，1，2，6，10，采用直接选择排序算法，当进行了两趟选择后，结果序列为（1，2，5，9，4，6，10）。39.广义表的（c，（b，a，b），f，e，（i，j），k）深度是（3）。40.广义表（a，b），d，e，（i，j），k）的长度是（4）。41.序列4，2，5，3，8，6，采用冒泡排序算法（升序），经一趟冒泡后，结果序列是（2，4，3，5，6，8）。42.广义表的（c，a，（a，b），d，e，（i，j），k）深度是（3） 。43.待排序的

8、序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后，结果序列为（1，2，4，8，3，5，9）。44.线性表用（顺序）方式存储需要占用连续的存储空间。45.线性表用（顺序）方式存储可以随机访问。46.线性表用关键字（有序）的顺序方式存储，可以用二分法排序。47.顺序表6，5，1，2，4，3，8，7经过一趟（1，1）归并后的结果序列为（5，6），（1，2），（3，4），（7，8）。二、单项选择题1.栈和队列的共同特点是（ ）。A. 都是先进后出B. 元素都可以随机进出C. 都是先进先出D. 都是操作受限的线性结构2.数据的存储结构包括数据元素的表示和（ ）。A. 数据元素的

9、类型B. 相关算法C. 数据处理的方法D. 数据元素间的关系的表示3.对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行：p=(struct node *)malloc(sizeof(struct node);p->data=a;和（ ）。A. top=top->next; p=top;B. p->next=top; p=top;C. p->next=top; top=p;D. top->next=p; p=top;4.树状结构中数据元素的位置之间存在（ ）的关系。A. 每一个元素都有一个直接前驱和一个直接后继B. 多对多C. 一对多D.

10、 一对一5.设头指针为head的非空的单向链表，指针p指向尾结点,则通过以下操作（ ）可使其成为单向循环链表。A. head = p;B. p->next = NULL ;C. p=head;D. p->next=head;6.设有一个长度为26的顺序表，要插入一个元素，并使它成为新表的第6个元素，需移动元素的个数为（ ）。A. 19B. 20C. 22D. 217.一种逻辑结构（ ）。A. 是指某一种数据元素的性质B. 只能有唯一的存储结构C. 可以有不同的存储结构D. 与存储该逻辑结构的计算机相关8.头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头

11、结点的单向循环链表，可执行head=head->nex;和（ ）。A. head->next=p->nextB. head->next=pC. p->next=head;D. p= head->next9.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ ）。A. 逻辑结构B. 存储结构C. 数据元素的存储D. 给数据元素分配存储空间10.元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。A. 111，113，115，117B. 117，115，111，113C. 117，115，113，11

12、1D. 113，111，117，11511.图状结构中数据元素的位置之间存在（ ）的关系。A. 每一个元素都有一个且只有一个直接前驱和一个直接后继B. 多对多C. 一对一D. 一对一12.以下说法正确的是（ ）。A. 栈和队列的特点都是后进后出B. 队列的特点是先进后出C. 栈的特点是先进先出D. 栈的特点是先进后出13.一个单链表中，在p所指结点之后插入一个s所指的结点时，可执行：s->next=p->next;和（ ）。A. s=p->next;B. p=s->next;C. p->next=s->next;D. p->next=s;14.设有一个

13、20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a6,2在一维数组B中的下标是（ ）。A. 23B. 21C. 17D. 2815.元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（ ）。（进栈出栈可以交替进行）。A. 14，12，18，16B. 18，16，12，14C. 12，14，16，18D. 18，16，14，1216.设有串p1="ABADF"，P2="ABAFD"，P3="ABADFA"，P4="ABAF

14、"，以下四个串中最大的是（ ）。A. p1B. p3C. p4D. p217.设有一个30阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（ ）。A. 41B. 38C. 32D. 1818.数组a经初始化char a =“English”;a7中存放的是（ ）。A. 变量hB. 字符hC. "h"D. 字符串的结束符19.设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（ ）。A. 22B. 15C. 24D. 1420.设主串为

15、“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。A. ABCB. BCdC. BcdD. Abc21.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。A. 2i+1B. 2iC. 2i-1D. 2i+222.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（ ）。A. 2iB. 2i+1C. 2i+2D. 2i-123.一棵具有16个结点的完全二叉树，共有（ ）层。（设根结点在第一层）A. 5B. 4C. 6D. 724.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. aebcfd

16、B. abecdfC. aedfcbD. aecbdf25.如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. acfebgdB. aedfcgbC. aebcfgdD. abecdfg26.线性表以（ ）方式存储，能进行折半查找。A. 链接B. 二叉树C. 关键字有序的顺序D. 顺序27.字符串“DABcdabcd321ABC”的子串是（ ）。A. “aBcd”B. “cd32”C. “321a”D. “ABcD”28.一棵具有38个结点的完全二叉树，最后一层有（ ）个结点。A. 5B. 7C. 6D. 829.如下图所示，若从顶点a出发，按广度

17、优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abcfgdeB. abcdfegC. abcdfgeD. acbfedg30.下图的拓扑序列是（ ）。A. 5 6 2 3 4B. 2 3 6 4 5C. 2 3 5 6 4D. 5 2 3 4 631.下面关于线性表的叙述错误的是（ ）。A. 线性表采用顺序存储便于插入和删除操作的实现B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储必须占用一片连续的存储空间32.设有头指针为head的不带头结点的非空的单向循环链表，指针p指向其尾结点，要删除第一个结点，则可

18、利用下述语句 head=head->next;和（ ）。A. p->next =head;B. p=NULL;C. head=p;D. p=head;33.以下数据结构中是非线性结构的是（ ）。A. 二叉树B. 队列C. 栈D. 线性表34.以下说法正确的是（ ）。A. 线性表的顺序存储结构不必占用连续的存储空间B. 一种逻辑结构只能有唯一的存储结构C. 线性表的链式存储结构必须占用连续的存储空间D. 一种逻辑结构可以有不同的存储结构35.设有一个长度为18的顺序表，要删除第7个元素需移动元素的个数为（ ）。A. 10B. 13C. 12D. 1136.把数据存储到计算机中，并具体

19、体现（ ）称为物理结构。A. 数据的运算B. 数据元素间的逻辑关系C. 数据的性质D. 数据的处理方法37.两个字符串相等的充要条件是（ ）。A. 两个字符串的长度相等B. 同时具备（A）和（C）两个条件C. 两个字符串中对应位置上的字符相等D. 以上答案都不对38.顺序表所具备的特点之一是（ ）。A. 插入元素的操作不需要移动元素B. 不需要占用连续的存储空间C. 可以随机访问任一结点D. 删除元素的操作不需要移动元素39.设某链表中最常用的操作是在链表的尾部插入或删除元素，在已知尾指针的条件下，选用下列（ ）存储方式最节省运算时间。A. 双向链表B. 双向循环链表C. 单向链表D. 单向循

20、环链表4.图状结构中数据元素的位置之间存在（ ）的关系。A. 一对一B. 多对多C. 一对多D. 每一个元素都有一个直接前驱和一个直接后继41.元素13，15，19，20顺序依次进栈，则该栈的不可能输出序列是（ ）。（进栈出栈可以交替进行）A. 13，15，19，20B. 15，13，20，19C. 19，13，15，20D. 20，19，15，1342.元素20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是（ ）。（进栈出栈可以交替进行）A. 20，14，16，18B. 14，20，18，16C. 18，16，20，14D. 18，16，14，2043.设指针q指向单链表中结点A

21、，指针p指向单链表中结点A的后继结点B，则在表中删除结点B的操作为（ ）。A. q->next=p->next；B. p->next；p=q；C. q->next=p；D. p->next=q->next；44.设有一个12阶的对称矩阵A（左上角第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4在一维数组B中的下标是（ ）。A. 12B. 11C. 13D. 1445.栈和队列的共同特点之一是（ ）。A. 都是先进后出B. 没有共同点C. 只允许在端点处插入和删除元素D. 都是先

22、进先出46.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（ ）。A. 25B. 23C. 14D. 1547.用链接方式存储的队列，在进行插入运算时（ ）。A. 头、尾指针都不需要修改B. 需修改尾指针C. 需修改头指针D. 头、尾指针都需要修改48.在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（ ）。A. 9B. 10C. 12D. 1149.字符串 a1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（ ）。A. a4B. a2C

23、. a3D. a150.一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（ ）个结点。A. 14B. 15C. 18D. 1951.设有一个20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a6,2在一维数组B中的下标是（ ）。A. 18B. 23C. 21D. 1752.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abcfgdeB. abcdfgeC. abcedfgD. acbfedg53.以下说法正确的是（ ）。A. 前序遍历二叉排序

24、树可得到一个有序序列。B. 若二叉树中左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点的值。则该树为二叉排序树。C. 二叉树中任意一个结点的值均大于其左孩子的值，小于其右孩子的值。则该树为二叉排序树。D. 二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值，小于其右子树上所有结点的值，则该树为二叉排序树。54.字符串"abcd321ABCD"的子串是（ ）。A. abcDB. "321a"C. "21ABC"D. "abcABCD"55.二叉树的第k层的结点数最多为（ ）。A. 2K+1

25、B. 2k-1C. 2k-1D. 2K-156.数组a经初始化char a =“English”;a1中存放的是（ ）。A. "n"B. "E"C. 字符nD. 字符E57.如下图所示，若从顶点6出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. 6，2，7，9，8，4，3B. 6，2，8，7，9，3，4C. 6，9，2，3，7，8，4D. 6，9，3，2，8，7，458.如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. aedfcbB. acfebdC. aebcfdD. abecdf

26、59.如下图所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abcdfgeB. abcfegdC. abcfgdeD. acbfedg60.下图的拓扑序列是（ ）。A. 2 3 4 5 6B. 5 6 4 2 3C. 5 2 3 4 6D. 5 2 3 6 4三、综合题1.有一个长度为11的有序表（1，2，11，15，24，28，30，56，69，70，80），元素的下标依次为：1，2，3，11，按折半查找对该表进行查找。（1）画出对上述查找表进行折半查找所对应的判定树。（2）说出成功查找到元素56，需要依次经过与哪些元素的比较？（3）说出不成功查找元素

27、72，需要进行元素比较的次数？参考答案：（1）（2）28，69，30，56（3）4次2.（1）以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。（2）给出相应权重值叶结点的哈夫曼编码。（2）n个叶结点的哈夫曼树，总共有多少个结点？参考答案：（1）（2）3：0004：0015：018：109：11（3）2n-13.（1）一组记录的关键字序列为（57，90，67，50，51，56），利用堆排序（堆顶元素是最小元素）的方法建立初始堆（要求以完全二叉树描述 ）。（2）对关键字序列（56，51，71，54，46，106）利用快速排序，以第一个关键字为分割元素，给出经过一次划分后结果。（3）一组记录

28、的关键字序列为（60，47，80，57，39，41，46，30），利用归并排序的方法，分别给出（1，1）归并、（2，2）归并、（4，4）归并的结果序列。参考答案：（1）（2）46，51，54，56，71，106（3）（47，60）（57，80）（39，41）（30，46）（47，57，60，80）（30，39，41，46）（30，39，41，46，47，57，60，80）4.（1）设有数据集合40，29，7，73，101，4，55，2，81，92，39，依次取集合中各数据构造一棵二叉排序树。（2）在上述二叉排序树上进行查找，给出成功查找到元素92的查找路径，其中共经过了多少次元素间的的比较。（

29、3）有一个长度为10的有序表，按折半查找对该表进行查找，给出在等概率情况下查找成功的平均比较次数为。参考答案：（1）（2）40，73，101，81，92。共5个元素比较（3）29/105.（1）以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树。（2）给出相应权重值叶结点的哈夫曼编码。（3）一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序的方法建立的初始堆（堆顶元素是最小元素，以树的形式给出）。参考答案：（1）（2）2：00003：00014：0017：108：119：01（3）6.（1）一组记录的关键字序列为（36，69，46，28，30，35），给出利用堆排序

30、（堆顶元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述 ）。（2）对关键字序列（36，69，46，28，30，74）采用快速排序，给出以第一个关键字为分割元素，经过一次划分后的结果。（3）设有数据集合30，73，101，4，8，9，2，81，依次取集合中各数据构造一棵二叉排序树。参考答案：（1）28，30，35，69，36，46 （2）30，28，36，46，69，74（3）7.（1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树。（2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、

31、d、e的大小关系。（3）给出该树的前序遍历序列。参考答案：（1）（2）d<b<e<a<c（3）abdec8.（1）一组记录的关键字序列为45，40，65，43，35，95，写出利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果（要求给出一趟划分中每次扫描和交换的结果）。（2）对序列45，40，65，43，35，95利用直接插入排序，写出逐次插入过程（从第一个元素一直到第六个元素）。参考答案：（1）（2）40 45 65 43 35 9540 43 45 65 35 9535 40 43 45 65 959.（1）设head1和p1分别是不带头结点的单向链表A的头

32、指针和尾指针，head2和p2分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个以head1为头指针的单向循环链表，写出其中两个关键的赋值语句（不用完整程序，结点的链域为next）。（2）单向链表的链域为next，设指针p指向单向链表中的某个结点，指针s指向一个要插入链表的新结点，现要把s所指结点插入p所指结点之后，某学生采用以下语句： p->next=s; s->next=p->next;这样做正确吗？若正确则回答正确，若不正确则说明应如何改写。参考答案：（1）p1->next= head2；p2->next= head1；（2）

33、不对，s->next= p->next；p->next=s；10.（1）设根为第1层,对给定权值1，3，4，4，5，6，构造深度为5的哈夫曼树。提示：构造中当出现被选的结点值有多个相等时，可尝试不同组合，以得到要求的树的深度。（2）求树的带权路径长度。（3）用链接法存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由？（4）给出对上述哈夫曼树中序遍历得到的的序列。（5）一棵哈夫曼树有n个非叶结点，构造该树共有多少个权重值？简述理由？参考答案：（1）（2）WPL=1*4+3*4+4*3+6*2+4*2+5*2=58（3）有12个空指针域，因为共11个结点，22个指针域，除根结

34、点外，每个结点对应一个指针域，共10个指 域非空，故有 22-10=12个空指针域。（针对哈夫曼树还可有其它理由）（4）1，4，3，8，4，14，6，23，4，9，5（5）n+1，因为叶结点比非叶结点多1。四、程序填空题1.以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。void Inorder(struct BTreeNode *BT) if(BT!=NULL) Inorder(BT->left) ; printf("%c",BT->data) ; Inorde

35、r(BT->right);利用上述程序对下图进行遍历，结果是 d b f e a c 。2.设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。struct node int data; struct node *next;typedef struct node NODE;#define NULL 0void main() NODE *head,*p; p=head; /*p为工作指针*/ do printf("%dn", p->data ); p=p->next ;

36、while( p!=NULL );3.以下冒泡法程序对存放在a1，a2，an中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。void bsort (NODE a ,int n) NODE temp; int i,j,flag; for(j=1; j<=n-1 ;j+) flag=0; for(i=1; i<=n-j ;i+) if(ai.key>ai+1.key) flag=1; temp=ai; ai=ai+1 ; ai+1=temp ; if(flag=0)break; 设有序列6，4，5，8，2，1，给出由该程序经过两趟冒泡后的结果序列 4，5

37、，2，1，6，8 。4.以下函数为直接选择排序算法，对a1，a2，an中的记录进行直接选择排序，完成程序中的空格：typedef struct int key; NODE;void selsort(NODE a ,int n) int i,j,k; NODE temp; for(i=1;i<= n-1 ;i+) k=i; for(j=i+1;j< n ;j+) if(aj.key<ak.key) k=j ; if(i!=k) temp=ai; ai=ak ; ak=temp ; 5.设线性表为（1，3，7，5），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。struct node int data; struct node *next;typedef struct node NODE;#define NULL 0void main() NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; c.data=4; /*d是尾结点*/ head= &a ; a.next=&b; b.next=&c; c.next=&d; d->next=NULL ; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do printf