下载文档原格式
一、单项选择题（每小题3分，共60分）题目1把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。
A. 物理结构题目2下列说法中，不正确的是（）。
C. 数据项可由若干个数据元素构成题目3一个存储结点存储一个（）。
C. 数据类型题目4数据结构中，与所使用的计算机无关的是数据的（）。
A. 逻辑结构题目5在线性表的顺序结构中，以下说法正确的是（）。
B. 逻辑上相邻的元素在物理位置上也相邻题目6对链表, 以下叙述中正确的是（）。
D. 不能随机访问任一结点题目7下列的叙述中，不属于算法特性的是（）。
B. 可读性题目8算法的时间复杂度与（）有关。
A. 算法本身题目9设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。
B. n-i+1题目10设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。
C. n-i题目11在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。
C. p->next=q->next题目12在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。
A. s->next=p->next; p->next=s;题目13非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。
A. p->next==head题目14链表不具有的特点是（）。
B. 可随机访问任一元素题目15带头结点的链表为空的判断条件是（）（设头指针为head）。
C. head->next==NULL题目16在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始从后到前依次移动了15个元素。
则原顺序表的长度为（）。
C. 20题目17有关线性表的正确说法是（）。
B. 除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继题目18向一个有127个元素的顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动（）个元素。
《数据结构（本）》期末综合练习题一、单选选择题1.栈和队列的共同特点是（C）。
A. 都是先进先出B. 都是操作受限的线性结构C. 都是先进后出D. 元素都可以随机进出2.数据的存储结构包括数据元素的表示和（C）。
A. 数据处理的方法B. 数据元素的类型C. 数据元素间的关系的表示D. 相关算法3.对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行p=(struct node *)malloc(sizeof(struct node);p->data=a;和（C）。
A. top->next=p; p=top;B. p->next=top; p=top;C. p->next=top; top=p;D. top=top->next; p=top;4.树状结构中数据元素的位置之间存在（B）的关系。
A. 每一个元素都有一个直接前驱和一个直接后继B. 一对多C. 一对一D. 多对多5.设头指针为head的非空的单向链表，指针p指向尾结点,则通过以下操作（D）可使其成为单向循环链表。
A. head = p;B. p=head;C. p->next = NULL ;D. p->next=head;6.设有一个长度为26的顺序表，要插入一个元素，并使它成为新表的第6个元素，需移动元素的个数为（D）。
A. 22B. 19C. 20D. 217.一种逻辑结构（C）。
A. 与存储该逻辑结构的计算机相关B. 是指某一种数据元素的性质C. 可以有不同的存储结构D. 只能有唯一的存储结构8.头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表，可执行head=head->nex;和（A）。
A. p->next=head;B. p= head->nextC. head->next=pD. head->next=p->next9.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（D）。
国家开放大学电大本科《数据结构》期末试题及答案（试卷号1252）2022-2022国家开放大学电大本科《数据结构》期末试题及答案（试卷号：1252）
盗传必究一、单项选择题（每小题3分，共30分）
三、综合题(每小题中每间6分,共30分)23.(1)设有数据集合
(0,39,17,83111,14,65,13,91,102,49),依次取集合中各数据构造一棵二叉排序树。
(2)一组记录的关键字序列为(6,9,7,4,5,8),利用堆排序(堆顶元素是最小元素)的方法建立初始堆。
(要求用完全二叉树表示)24.(1)如下为一个长度为10的有序表,给出按折半查找对该表进行查找的判定树。
(2)按折半查找对该表进行查找,求在等概率情况下查找成功的平均比较次数。
四、程序填空题(每空2分,共16分)25.设线性表以不带头结点的单向链表存储,链表头指针为head,以下程序的功能是:(1)输出链表中各结点中的数据城data.(2)把该单向链表改为以p作为尾指针的单向循环链表。
(链表中结点的指针域为next,数据域为data)。
试题答案及评分标准（仅供参考）。
一、单项选择题1.深度为５得完全二叉树共有20个结点,则第5层上有（)个结点（根所在结点为第一层)。
A.3 Ｂ。
８ C.5D。
62．同一种逻辑结构( ).A.只能有唯一得存储结构B。
可以有不同得存储结构C。
只能表示某一种数据元素之间得关系D．以上三种说法均不正确３．已知一个图得边数为m，则该图得所有顶点得度数之与为（）.Ａ.2m B。
ｍC。
2ｍ+1 Ｄ。
m／2 4。
链表所具备得特点就是( ）.A．可以随机访问任一结点B.占用连续得存储空间C.插入删除元素得操作不需要移动元素结点D。
可以通过下标对链表进行直接访问5．数据结构中，与所使用得计算机无关得就是数据得（ )结构。
A．物理 B．存储Ｃ.逻辑与物理Ｄ。
逻辑6．数据得物理结构（）。
Ａ．与数据得逻辑结构无关Ｂ．仅仅包括数据元素得表示C.只包括数据元素间关系得表示D。
包括数据元素得表示与关系得表示7。
链表所具备得特点就是（)。
A.可以随机访问任一结点B.占用连续得存储空间C.插入删除不需要移动元素结点D．可以通过下标对链表进行直接访问8。
线性结构中数据元素得位置之间存在（）得关系。
A。
一对一 B.一对多C．多对多Ｄ.每一个元素都有一个直接前驱与一个直接后继９.线性表只要以（)方式存储就能进行折半查找.A.链接B。
顺序C。
关键字有序得顺序Ｄ.二叉树10.以下表中可以随机访问得就是（）.A.单向链表B.双向链表C。
单向循环链表D．顺序表１1。
散列查找得原理就是（）。
Ａ．在待查记录得关键字值与该记录得存储位置之间建立确定得对应关系B.按待查记录得关键字有序得顺序方式存储C。
按关键字值得比较进行查找D．基于二分查找得方法12。
算法得时间复杂度与( ）有关.A．所使用得计算机 B.与计算机得操作系统C.与算法本身 D．与数据结构１3．对n个元素进行冒泡排序若某趟冒泡中只进行了（）次元素间得交换，则表明序列已经排好序。
Ａ．1 B．２C．0 D．ｎ-114。
设有一个长度为n 得顺序表,要删除第i 个元素需移动元素得个数为（ ）。
国家开放大学《数据结构（本）》形考作业1-4参考答案形考作业1一、单项选择题（每小题3分，共60分）1.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。
A. 算法的具体实现B. 物理结构C. 逻辑结构D. 给相关变量分配存储单元2.下列说法中，不正确的是（）。
A. 数据项是数据中不可分割的最小可标识单位B. 数据元素是数据的基本单位C. 数据项可由若干个数据元素构成D. 数据可有若干个数据元素构成3.一个存储结点存储一个（）。
A. 数据结构B. 数据元素C. 数据类型D. 数据项4.数据结构中，与所使用的计算机无关的是数据的（）。
A. 物理和存储结构B. 物理结构C. 逻辑结构D. 存储结构5.在线性表的顺序结构中，以下说法正确的是（）。
A. 逻辑上相邻的元素在物理位置上不一定相邻B. 逻辑上相邻的元素在物理位置上也相邻C. 进行数据元素的插入、删除效率较高D. 数据元素是不能随机访问的6.对链表, 以下叙述中正确的是（）。
A. 结点占用的存储空间是连续的B. 插入删除元素的操作一定要要移动结点C. 可以通过下标对链表进行直接访问D. 不能随机访问任一结点7.下列的叙述中，不属于算法特性的是（）。
A. 可读性B. 输入性C. 可行性D. 有穷性8.算法的时间复杂度与（）有关。
A. 算法本身B. 计算机的操作系统C. 数据结构D. 所使用的计算机9.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。
A. n-i+1B. n-i-1C. n-iD. i10.设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。
A. iB. n-iC. n-i-1D. n-i+111.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。
A. p->next=q->nextB. p=q->nextC. p->next=qD. q->next=NULL12.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。
数据结构（本）期末综合练习2017年5月有得看就不难综合练习一一、单项选择题1．设有头指针为head的带有头结点的非空单向循环链表, 指针p指向其尾结点, 要删除头结点,并使其仍为单向循环链表,则可利用下述语句head =head->next ;（）。
A．p =head; B．p=NULL; C．p->next =head; D．head=p;2．在一个单链表中p指向结点a, q指向结点a的直接后继结点b，要删除结点b，可执行（）。
A．p->next=q->next ; B．p=q->next;C．p->next=q; D．p->next=q;3. 以下说法不正确的是A. 线性表的链式存储结构不必占用连续的存储空间B．一种逻辑结构只能有唯一的存储结构C. 一种逻辑结构可以有不同的存储结构D．线性表的顺序存储结构必须占用连续的存储空间4．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行（）;和p->next=s;A．p= s; B． p->next=s->next;C．p=s->next; D． s->next=p->next;5．把数据存储到计算机中，并具体体现( )称为物理结构。
A. 数据元素间的逻辑关系B．数据的处理方法C．数据的性质D．数据的运算6．设有一个长度为23的顺序表，要删除第8个元素需移动元素的个数为（）。
A．16 B．14 C．15 D．137．链表所具备的特点之一是（）。
A．可以随机访问任一结点 B．需要占用连续的存储空间C．插入元素的操作不需要移动元素 D．删除元素的操作需要移动元素8．设一棵有8个叶结点的二叉树，度数为1的结点有3个,则该树共有（）个结点。
A．20 B．18 C．17 D．169．图状结构中数据元素的位置之间存在（）的关系。
A．一对一 B．多对多C．一对多 D．每一个元素都有一个直接前驱和一个直接后继10．一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。
A．14 B．15 C．19 D．18 11．元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。
A．13，11，9，15 B．15，9，11，13C．13，11，15，9 D．9， 15，13，1112.设主串为“FABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（）。
A. EFaBcB. ABCdEC. DABCC D .FAbcC13．设有一个14阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a4,3在一维数组B中的下标是（）。
A．9 B．10 C．11 D．814．元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。
A．117，115，113，111 B．111，113，115，117 C．113，111，117，115 D．117，115，111，11315．在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（）。
A．18 B．16 C．15 D．1716．以下说法不正确的是（）。
A．栈和队列都是线性结构 B．栈的特点是后进先出C. 栈和队列的特点都是先进后出 D．队列的特点是先进先出17．设一棵哈夫曼树共有14个非叶结点，则该树总共有（）个结点。
A．29 B.27 C．30 D．28 18．设有一个15阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a4,2在一维数组B中的下标是（）。
A．9 B．8 C．7 D．1019．如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。
A．abecdf B．acfebd C．aebcfd D．aedbfc图120．如图2所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。
A．acedbf B．acebfd C．aebcfd D．aedfcb图2二、填空题1. 队列的特点之一是：元素进、出队的次序是:先进_______。
2. 序列13,11,14,12,17,15,采用冒泡排序算法,经一趟冒泡后,序列的结果是________。
3．________结构中，数据元素间存在一对多的关系。
4. 对16个元素的序列用冒泡排法进行排序，通常需要进行________趟冒泡。
5．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是____ ___。
6. 对9个元素的一组记录（58，35，93，20，12，78，56，41，79）进行直接插入排序(由小到大排序) ，当把第7个记录56插入有序表，为寻找插入位置需比较________次。
7．在对11个记录的序列(12，35, 9, 7 ,2, 11 ,56 , 95 ,37,58 ,60)进行直接插入排序时，当把第6个记录11 插入到有序表时，为寻找插入位置，元素间需比较_________次。
（由小到大排列）8．结构中的数据元素存在一对多的关系称为________结构。
9．哈希函数是记录关键字的值与该记录___ ___之间所构造的对应关系。
10．设有一棵深度为5的完全二叉树，第5层上有3个结点，该树共有_______个结点。
（根所在结点为第1层）11．20个元素进行冒泡法排序，通常需要进行19趟冒泡,其中第10趟冒泡共需要进行____ ____次元素间的比较。
12．一棵二叉树中每一个非叶结点的度数都为2，共有10个非叶结点，则该树共有_______ 个结点。
13．一棵有19个结点的二叉树,采用链式结构存储,该树结构中有_____ 个指针域为空。
14. 序列3,1,7,18,6,9,13,12经一趟归并排序的结果为__ __ __。
15．中序遍历一棵________树可得到一个有序序列。
16．一棵有16个叶结点的哈夫曼树，则该树共有_______个非叶结点。
17．二叉排序树插入操作中,新插入的结点总是以树的________ 结点被插入的18．________遍历二叉排序树可得到一个有序序列。
19. 广义表的( a , (d,a ,b) , h , (e ,( (i ,j ) ,k )) )深度是________ 。
20. 广义表( f , h , (a ,b, d, c) , d , e ,( (i ,j ) ,k ) )的长度是______ __。
21. 序列4 , 2 , 5 , 3 , 8 , 6 , 7, 9,采用归并排序算法(升序),经一趟归并后,序列的结果_______ _。
22. 广义表的( h ,c ，g, a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是__ _____。
23. 字符串a1=〝teijing 〞, a2 =〝tef 〞 , a3= 〝teifang 〞, a4=“tefi 〞最小的 是 ________。
24．设有串p1=”ABADF ”,P2=”ABAFD ”，P3=”ABADFA ”P4=”ABAF ”, 四个串中最 小的是 ________ 。
三、综合题1．设查找表为（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）（2）说明成功查找到元素86需要经过多少次比较？（3）求在等概率条件下，成功查找的平均比较次数？2.（1）设有数据集合{50，39，17，83，111，14，65，13，91，102，49}，依次取 集合中各数据构造一棵二叉排序树。
(2) 一组记录的关键字序列为（6，9，7，4，5，8），利用堆排序（堆顶元 素 是最小元素）的方法建立初始堆。
(要求用完全二叉树表示)3.(1) 一组记录的关键字序列为（26，59，36，18，20，25），给出利用堆排序（堆顶 元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述 ）。
(2) 对关键字序列(26,59,36,18,20,64)采用快速排序，给出以第一个关键字为分割 元素，经过一次划分后的结果。
4. (1) 如下表为一个长度为10的有序表，给出按折半查找对该表进行查找的判定树(2) 按折半查找对该表进行查找，求在等概率情况下查找成功的平均比较次数。
为了成功查找72 ,给出元素的比较次数。
5．(1) 以1，2，3 ，6，7，8作为叶结点的权，构造一棵哈夫曼树(2) 给出具有相应权重值的叶结点的哈夫曼编码。
四、程序填空题1．以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k 的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedefstruct{ int key;……}NODE;int Binary_Search(NODE a[ ], int n, int k){int low, mid, high;low=0;high=n-1;while(__(1)______){mid=(__(2)______)if(a[mid].key==k)return __(3)______;else if (__(4)______)low=mid+1;else __(5)______;}return -1}2.设线性表以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。
完成程序中空格部分。
#define NULL 0void main( ){ NODE *head ,*p ;p=head; /*p为工作指针*/do{printf(“%d\n”, ___(1)_____);___(2)_____ ;}while(___(3)_____);}3.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Inorder (struct BTreeNode *BT){if(BT!=NULL){__(1)______;__(2)______;Inorder(BT-- >right);}}利用上述程序对右图进行前序遍历，结果是__(3)______;4.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
完成程序中空格部分。
void Inorder (struct BTreeNode *BT){if( BT!=NULL){Inorder(BT->left);___(1)________(2)_____}5. 顺序查找算法如下, 完成程序中空格部分。
