《数据结构》模拟试题3
一、单项选择题
1．带头结点的单向链表为空的判断条件是（）（设头指针为head）。
A．head = =NULL B．head!=NULL
C．head->next= =head D．head->next= =NULL
2．非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。
A．p->next = =NULL B．p= =NULL C．p= =head D．p->next= =head 3．算法的时间复杂度与（）有关。
A．所使用的计算机 B．计算机的操作系统
C．算法本身 D．数据结构
4．设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（）。
A．n-i+1 B．n-i C．n-i-1 D．i
5．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。
A．p=s→next B．p→next=s→next;
C．s→next=p→next; p→next=s; D．p→next= s; s→next= p→next
6．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。 A．r=f→next; B．r=r→next; C．f=f→next; D．f=r→next;
7．元素1，3，5，7按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。
A．7，5，3，1 B．7，5，1，3
C．3，1，7，5 D．1，3，5，7
8．在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。
A．4 B．3 C．6 D．12
9．在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）。
A．2i B．2i-1 C．2i+1 D．2i+2
10．一棵具有35个结点的完全二叉树，最后一层有（）个结点。
A．4 B．6 C．16 D．8
11．在一个无向图中，所有顶点的度数之和等于边数的（）倍。
A．3 B．2 C．2.5 D．1.5
12．已知如图3所示的一个图，若从顶点V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（）。
A．V1V2V4V8V5V3V6V7 B．V1V2V4V5V8V3V6V7
C．V1V2V4V8V3V5V6V7 D．V1V3V6V7V2V4V5V8
图3
13．对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列。
A．按层次 B．后序 C．中序 D．前序
14．设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过一次元素的交换就使第m+1个元素排序到位，该方法是（）。
A．折半排序 B．冒泡排序 C．归并排序 D．简单选择排序
15．一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）。
A．39，47，46，80，41，57 B．39，41，46，80，47，57
C．41，39，46，47，57，80 D．39，80，46，47，41，57
二．填空题
1．算法的5个特征为_________。
2．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为________和________ 。
3．在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行s->next=p->next;和的操作。
4．在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作________。
5．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s->next=h; 和操作。(结点的指针域为next)
6．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为r->next=s;和(结点的指针域为next)。
7.两个串相等的充分必要条件是_______ ___。
8．在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_______、、。
9．一棵二叉树中有2n-2条边（结点间的连线），其中每一个非叶结点的度数都为2，则该树共有_______个非叶结点。
10．如图1所示的二叉树，其中序遍历序列为________ _。
11．如图1所示的二叉树，其后序遍历序列为_________。
12．哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。
13．n 个元素进行冒泡法排序，通常需要进行________趟冒泡，第j 趟冒泡要进行______次元素间的比较。
三、综合题
1．已知序列{11，19，5，4，7，13，2，10}
（1）试给出用归并排序法对该序列作升序排序时的每一趟的结果。
（2）对上述序列用堆排序的方法建立初始堆（要求小根堆，以二叉树描述建堆过程）。 2．设查找表为(7,15,21,22,40,58,68,80,88,89,120) ,元素的下标依次为1,2,3,……，11. （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示） （2）说明成功查找到元素40需要经过多少次比较？ （3）求在等概率条件下，成功查找的平均比较次数？ 3．
（1）如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。 （2）设有数据集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各数据，构造一棵二叉排序树. 4．
(1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则说明理由？
(2)设有查找表{7，16，4，8，20，9，6，18，5}，依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果. 5．（1）对给定权值2，1，3，3，4，5，构造哈夫曼树。
（2）同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。
四、程序填空题
1．以下是用尾插法建立带头结点且有n 个结点的单向链表的程序，结点中的数据域从前向
图1 图2
后依次为1,2,3,……,n，完成程序中空格部分。
NODE *create(n)
{NODE *head , *p, *q;
int i;
p=(NODE*)malloc(sizeof(NODE));
head= ①; ②;p→next=NULL; /*建立头结点*/
for(i=1; i<=n; i++)
{ p= ③;
p->data=i;
p->next=NULL;
q->next= ④;
⑤;
}
return(head);
}
2．设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。
#define NULL 0
void main( )
{NODE a,b,c,d,*head,*p;
a.data=6;
b.data=10;
c.data=16;
d.data=4; /*d是尾结点*/
head= ①;
a.next=&b;
b.next=&c;
c.next=&d;
②; /*以上结束建表过程*/
p=head; /*p为工作指针，准备输出链表*/
do
{printf(“%d\n”, ③);
④;
}while( ⑤);
}
3．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Inorder (struct BTreeNode *BT)
{ if(BT!=NULL){
①;
②;
③;
}
}
4．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右
指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Inorder (struct BTreeNode *BT)
{
if(BT!=NULL){
（1）;
（2）;
Inorder(BT->right);}
}
利用上述程序对右图进行遍历，结果是 ;
综合练习题答案
一、单项选择题
1．D 2．D 3．C 4．B 5．C 6．C 7．B 8．A 9．A 10．A 11．B 12．A 13．C 14．D 15．B
二、填空题
1．有穷性、确定性、可行性、零个或多个输入、一个或多个输入
2．n-1,O(n)
3．s->next=p->next;
4．q->next=p->next;
5．s->next=h;
6．r->next=s;
7．串长度相等且对应位置的字符相等
8．值域、左指针、右指针
9．n-1
10．dgbaechif
11．gdbeihfca
12．存储地址
13．n-1,n-j
三、综合题
1．
(1) 初始11，19，5，4，7，13，2，10
第一趟[ 11，19][4，5][7，13][2，10]
第二趟[4，5，11，19][2，7，10，，13]
第三趟[2，4，5，7，11，10，11，13]
(2)
2． (1)
(2)4次
(3)ASL=(1+2*2+3*4+4*4)/11=3
3．
(1)不正确，例 (2)
4．
(1)不正确，二叉排序树要求其子树也是二叉排序树。 (2)
后续遍历 5，6，4，9，8，18，20，16，7
5．（1）
wpl1=45
（2）
wpl2=45
四、程序填空题 1． ①p
②q=p
③(NODE*)malloc(sizeof(NODE)) ④p ⑤q=p
2． ①&a
②d →next= =NULL ③p →data ④p =p →next ⑤p!=NULL
3． ① Inorder(BT->left);
② printf(“%c ”,BT->data);
③ Inorder(BT->right);
4．① Inorder(BT->left);
② printf(“%c”,BT->data);
③dbeafc
数据结构模拟题及答案 一、填空题（每小题 1 分，共 20 分）： 1、栈是一种 _____________的线性表，队列是一种_____________的线性表(要求填特性)。 2、___________________是数据的基本单位，可由若干个_______________ 组成，______________是数据的最小单位。 3、具有 354个结点的完全二叉树深度为 ________________，树中度为1的结点数为______________。 4、数组的运算有______________________________________ 和____________________________。 5、稀疏矩阵的压缩存储一般采用_____________________________存储方式。 6、广义表运算：tail ((( a, b ), ( c , ( d, e )))) = _______________________ 。 7、数据结构中评价算法的两个重要指标是__________ 、__________ 。 8、一个算法具有 5个特性: 、、，有零个或多个输入、有一个或多个输出。
9、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是: 。 10、Prim（普里姆）算法适用于求______ 的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求 ______ 的网的最小生成树。 11、 N个顶点的连通图的生成树含有 ______ 条边。 12、顺序查找 n个元素的顺序表，若查找成功，则比较关键字的次数最多为 __ __ 次；当使用监视哨时，若查找失败，则比较关键字的次数为_ _ __ 。 13、若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的 __________ 和记录的 _________ 。 14、直接插入排序用监视哨的作用是 ___________________。 15、一个字符串中 ________________ 称为该串的子串。 16 . 广义表(a,(a,b),d,e,((i,j),k))的长度是 _ ，深度是 _ 。 17. 在二叉树中，指针p所指结点为叶子结点的条件是 ______ 。 18. 有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是 _ __ ，带权路径长度WPL为 _ __ 。 19. 求图的最小生成树有两种算法，______ 算法适合于求稀疏图的最小生成树。
模拟试卷三 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结 点的度的总和是_____________。 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由 算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的
练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2
数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。
A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆
数据结构模拟试题三 一．判断题（每小题1 分，共10分） 1.逻辑结构不同的数据，要采用不同的存储方法来存储。 2.单链表中的结点只有后继，没有前驱。 3.栈和队列具有相同的逻辑特性。 4.二叉树中结点之间的相互关系不能用二元组来表示。 5.关键路径是由权值最大的边构成的。 6.在表示矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小无关。 7.在广义表中，每个原子必须是单个字符。 8.在平衡二叉排序树中，每个结点的平衡因子值是相等的。 9.只有在线性表的初始状态为逆序排列的情况下，起泡排序过程中，元素的移动次数才会 达到最大值。 10.在B+树上可以进行顺序查找。 二．填空题（每空1分，共10分） 1.若用不带表头结点的单链表来表示链接队列，则只有在________情况下，插入操作既要 修改队尾指针的值，也要修改队头指针的值;只有在________情况下，删除操作仅需修改队首指针的值，不需修改队尾指针的值。 2.无向图中边的数目等于邻接矩阵中___________。 3.在各元素查找概率相等的情况下，在含有12个元素的二叉排序树上查找其中一个元素， 元素间的平均比较次数至少是____次，至多是____次。 4.对12个元素进行快速排序，排序码的比较次数最多是___次。 5.对B+树来说，若某个非根分支结点中有6个关键字，则在它的某个孩子结点中至少有 _____个关键字，至多有_____个关键字。 6.如果在根结点中要查到要找的关键字，则对于B-树来说，下一步应该_________，而对 于B+树来说，下一步应该_________。 三．单选题（每题2分，共20分） 1.线性结构采用链式存储，________。 A．对插入、删除结点的操作较为有利B．不利于进行顺序访问 C．逻辑上相邻的结点在存储器中也相邻D．可以用一些不连续的存储区域来存放一个结点2. 某算法的时间复杂度为O（2n），表明该算法的________。 A．执行时间与2n成正比B．执行时间等于2n C．问题规模是2n D．问题规模与2n成正比 3. 在长度为n的_________上，删除最后一个元素，其算法的时间复杂度是O(n)。 A．只有表头指针的循环双向链表B．只有表头指针的非循环双向链表 C．只有表尾指针的非循环双向链表 D . 只有表尾指针的循环双向链表 4. 在4个元素的进栈序列给定以后，由这4个元素构成的可能出栈序列共有________种。A．14 B.16 C.17 D.24 5. 在任何一棵二叉树中，如果结点a有左孩子b、右孩子c，则在结点的前序序列、中序序列、后序序列中，_____________。 A．结点b一定在a的前面B．结点a一定在结点c的前面C．结点b一定在结点c的前面D．结点a一定在结点b的前面 6.若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是_____________。A．dbacef B. acbedfC.efbacd D. bafdce 7. 对稀疏矩阵采用压缩存储，其优点之一是可以_____________。 A．减少非零元素的存储空间B．不减少访问非零元素所需时间 C．减少矩阵的存储空间D．降低非零元素间逻辑关系的复杂程度 8. 设待查找元素关键字的值是47，且已存入变量k中，如果在查找过程中，和k进行比较的关键字值依次是82,72,36,84,47，则所采用的查找方法可能是____________。 A．顺序查找B．分块查找C．折半查找D．平衡二叉排序树查找 9．在线性表中元素很多且各元素逆序排列的情况下，执行_______排序，元素的移动次数最
试卷一 一、选择题（本题共30分,每题2分） 1. 计算机识别、存储和加工处理的对象被统称为________。 A. 数据 B. 数据元素 C. 数据结构 D. 数据类型 2. 已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列________。 A．1234 B．4321 C．2143 D．4123 3.链表不具有的特点是________。 A. 随机访问 B. 不必事先估计所需存储空间大小 C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比 4. 设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。经过以下队列操作后，队头的值是________ InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); EnQueue(Q,c); DeQueue(Q,x) A. a B. b C.NULL D.x 5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行________。 A．p=q->next; p->next=q->next;free(p); B．p=q->next; q->next=p; free(p); C．p=q->next; q->next=p->next; free(p); D．q->next=q->next->next; q->next=q; free(p); 6. 一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是________。 A．110 B．108 C．100 D．120 7. 在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是________。 A. n-i B. n-i+1 C. n-i-1 D. i 8．下面关于线性表的叙述错误的是________。 A. 线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D.线性表采用顺序存储便于插入和删除操作的实现 9. Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是________。 A.Push(A) Push(B) Pop(A) Pop(B) B.Push(A) Push(B) Pop(B) Pop(A) C.Push(A) Pop(B) Push(B) Pop(A) D.Push(B) Pop(A) Push(A) Pop(B) 10.下列查找方法中哪一种不适合元素的链式存储结构________。 A．顺序查找 B．分块查找 C．二分查找 D．散列查找 11. 下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是________。 A.快速排序 B.希尔排序 C.堆排序 D.冒泡排序 12. 设一棵二叉树的深度为k，则该二叉树中最多有________个结点。 A． 2k-1 B. 2k C. 2k-1 D. 2k-1
数据结构试题(A05) 一、选择题(共10小题，每小题1分，共10分) 1.下面程序段的时间复杂度是( ) m=0; for(i=1;i<=n;i++) for(j=1;j< = n;j++) m=m+1； A. O(n2) B.O(m + n + 1) C.O(m + n) D. O(n) 2.在单链表中，指针p指向元素为x的结点，实现〃删除x的后继〃的语句是() A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在长度为n的顺序表，当在任何位置上删除一个元素的概率相等时，删除一个 元素需要移动的元素的平均个数为( ) A.n/2 B.(n-1)/ 2 C.(n + 1)/2 D.(n+2)/2 4.一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是 () A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 6.设循环队列中数组的下标范围是1~n,其头尾指针分别为f和「，则其元素个数为( ) A.r-f C. (r-f) mod n + 1 B.r-f+1 D. (r-f+n) mod n 7.以下序列不是堆的是( )。
A.( 100 ,85,98,77,80,60,82,40,20,10,66) B.( 100 ,98,85,82,80,77,66,60,40,20,10) C.( 100 ,85,40,77,80,60,66,98,82,10,20 ) D.( 10,20,40,60,66,77,80,82,85,98, 100 ) 8 .在有序表( 12,24,36,48,60,72,84)中折半查找关键字72时所需进行的关键字比较次数为( )。 A. 3 B. 4 C. 5 D. 2 9.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 A.选择排序 B.冒泡排序 C.快速排序口.插入排序 二、填空题(共20小题，每小题1分，共20分) 1、在单链表中，删除指针P所指结点的后继结点的语句 是。 2、线性表的两种存储结构分别是和。 3、己知完全二叉树的第4层有5个结点，则其叶子结点数是。 4、将下三角矩阵A[1….8,1….8]的下三角部分逐行地存储到起始地址为1000 的内存单元中，已知每个元素占4个单元，则A[7 , 5]的地址是。 5、有n个结点的强连通有向图G至少有条弧。 7、在有序表A[1….20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较的元素的下标依次为。 8、直接选择排序算法所执行的元素交换次数最多为。 9、在带有头结点的单链表L中，第一个元素结点的指针
数据结构习题答案全真模拟题试题 第一章概论 一、名词解释 数据表示2.数据处理3.数据4.数据元素5.逻辑关系6.逻辑结构7.结构 8.运算9.基本运算10.存储结构11.顺序存储结构12.链式存储结构 13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的程序可执行部分 17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构 二、填空题 1.计算机专业人员必须完成的两项基本任务是：_________和__________。 2.数据在计算机存储器中的存在形式称为_________。 3.概括地说，数据结构课程的主要内容包括: 数据的__________、定义在_________、数据的__________的实现。此外，该课程还要考虑各种结构和实现方法的__________。 4.由一种__________结构和一组__________构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。 5.存储结构是逻辑结构的__________实现。 6.数据表示任务是逐步完成的，即数据表示形式的变化过程是__________->__________->__________。 7.数据处理任务也是逐步完成的，即转化过程是__________->__________->__________。 8.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__________、__________和__________。 9.根据需要，数据元素又被称为__________、__________、__________或__________。
《数据结构》模拟试题3 一、单项选择题 1．带头结点的单向链表为空的判断条件是（）（设头指针为head）。 A．head = =NULL B．head!=NULL C．head->next= =head D．head->next= =NULL 2．非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。 A．p->next = =NULL B．p= =NULL C．p= =head D．p->next= =head 3．算法的时间复杂度与（）有关。 A．所使用的计算机 B．计算机的操作系统 C．算法本身 D．数据结构 4．设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（）。 A．n-i+1 B．n-i C．n-i-1 D．i 5．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。 A．p=s→next B．p→next=s→next; C．s→next=p→next; p→next=s; D．p→next= s; s→next= p→next 6．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。 A．r=f→next; B．r=r→next; C．f=f→next; D．f=r→next; 7．元素1，3，5，7按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。 A．7，5，3，1 B．7，5，1，3 C．3，1，7，5 D．1，3，5，7 8．在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。 A．4 B．3 C．6 D．12 9．在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）。 A．2i B．2i-1 C．2i+1 D．2i+2 10．一棵具有35个结点的完全二叉树，最后一层有（）个结点。 A．4 B．6 C．16 D．8 11．在一个无向图中，所有顶点的度数之和等于边数的（）倍。 A．3 B．2 C．2.5 D．1.5 12．已知如图3所示的一个图，若从顶点V1出发，按广度优先法进行遍历，则可能得到的一种顶点序列为（）。 A．V1V2V4V8V5V3V6V7 B．V1V2V4V5V8V3V6V7 C．V1V2V4V8V3V5V6V7 D．V1V3V6V7V2V4V5V8
模拟试题三 模拟试题三 一、选择题（30分） 1.下面程序的时间复杂度为( )。 for(i=O;i
数据结构试卷（一）王彬 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。c A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( d ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（ c d）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：____ ____、________、________和_______。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为_________，树的度为________。 4.后缀算式9 2 3 +- 10 2 / -的值为________。中缀算式（3+4X）-2Y/3对应的后缀算 式为______3 4X* + 2Y* / -_________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有_______个指针域，其中有________个指针域是存放了地址，有______________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有______个和______个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有_____条边，在一个具有n个顶点的有向 完全图中，包含有_____条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为__________________________、______________、_____________________和_____________________。
《数据结构》模拟试题13 一、填空题（每小题2分，共18分） 1、数据的逻辑结构包括，和三种结构。 2、队列是操作受限的线性结构，只能在插入元素，而在删除元素。 3、串是一种特殊的线性表，其特殊性体现在。 4、有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形 到一个一维数组中，A[0][0]的地址是100（每个元素占2个基本存储单元），则A[5][9]的地址是。 5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数 至少为。 6、对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的大小为 ，邻接表中的结点总数为。 7、对线性表进行二分查找时，要求线性表必须是，且要 求。 8、对于文件，按物理结构划分，可分为顺序文件、文件、 文件和多关键字文件。 9、外部排序的最基本方法是，其主要时间花费在方面。 二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分） 1、如下函数是求1!+2!+…+n!，其时间复杂度是（）。 Long int Sum (int n) { long int sum=0 , t=1 ; int p ; for (p=1; p<=n ;p++) { t=t*p ; sum+=t ; } return(sum) ; } （A）O(n) （B）O(n2) （C）O(㏒2n) （D）O(n㏒2n) 2、设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（）。 （A）p=S[top++]；（B）p=S[++top]； (C)p=S[top--]；（D）p=S[--top]；
2020年考研计算机数据结构模拟试题及答案(三) 一、选择题(30分) 1. 1. 字符串的长度是指( )。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C) 串中所含字符的个数 (D) 串中不同数字的个数 2. 2. 建立一个长度为n的有序单链表的时间复杂度为( ) (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n) 3. 3. 两个字符串相等的充要条件是( )。 (A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符 相等 (C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对 4. 4. 设某散列表的长度为100，散列函数H(k)=k % P，则P通 常情况下选择( )。 (A) 99 (B) 97 (C) 91 (D) 93 5. 5. 在二叉排序树中插入一个关键字值的平均时间复杂度为( )。 (A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2) 6. 6. 设一个顺序有序表A[1：14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。 (A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4] (C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4] 7. 7. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度 为( )。
(A) 8 (B) 7 (C) 6 (D) 5 8. 8. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有( )个度数为0的结点。 (A) 5 (B) 6 (C) 7 (D) 8 9. 9. 设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b， e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发实行深度优先遍历能 够得到的一种顶点序列为( )。 (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc 10. 10. 队列是一种( )的线性表。 (A) 先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除 二、判断题(20分) 1. 1. 如果两个关键字的值不等但哈希函数值相等，则称这两个 关键字为同义词。( ) 2. 2. 设初始记录关键字基本有序，则快速排序算法的时间复杂 度为O(nlog2n)。( ) 3. 3. 分块查找的基本思想是首先在索引表中实行查找，以便确 定给定的关键字可能存有的块号，然后再在相对应的块内实行顺序查找。( ) 4. 4. 二维数组和多维数组均不是特殊的线性结构。( ) 5. 5. 向二叉排序树中插入一个结点需要比较的次数可能大于该 二叉树的高度。( ) 6. 6. 如果某个有向图的邻接表中第i条单链表为空，则第i个 顶点的出度为零。( ) 7. 7. 非空的双向循环链表中任何结点的前驱指针均不为空。( )
[ 数据结构II 模拟试题3 ] 一、单选题（每小题2分，共10小题，20分） 1. 若将数据结构形式定义为二元组(K ，R)，其中K 是数据元素的有限集合，则R 是K 上 A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2．下述程序段中语句①的频度是 s=0; for(i=1;i
《数据结构》模拟试题03 一、单项选择题（每题 2 分，共30分） 1．算法指的是（ ） A ．计算机程序 B ．解决问题的计算方法 C ．排序算法 D ．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A ．必须是不连续的 B ．连续与否均可 C ．必须是连续的 D ．和头结点的存储地址相连续 3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（ ） A ．O （1） B ．O （n ） C ．O （m ） D ．O （m+n ） 4．由两个栈共享一个向量空间的好处是：（ ） A ．减少存取时间，降低下溢发生的机率 B ．节省存储空间，降低上溢发生的机率 C ．减少存取时间，降低上溢发生的机率 D ．节省存储空间，降低下溢发生的机率 5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为（ ） A ．front=front+1 B ．front=(front+1)%(m-1) C ．front=(front-1)%m D ．front=(front+1)%m 6．如下陈述中正确的是（ ） A ．串是一种特殊的线性表 B ．串的长度必须大于零 C ．串中元素只能是字母 D ．空串就是空白串 7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ） A ．O （n 3） B ．O （n ） C ．O （n2） D ．O （n3） 8．一个非空广义表的表头（ ） A ．不可能是子表 B ．只能是子表 C ．只能是原子 D ．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表 对应的稀疏矩阵是（ ） 5
数据结构习题三 与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )。 [单选题] * A. 存储结构 B. 逻辑结构(正确答案) C. 类型 D. 运算实现 时间复杂度的阶数中，O(n)表示( )。 [单选题] * A. 常数阶 B. 线性阶(正确答案) C. 多项式阶 D. 指数阶 数据的逻辑结构分为四种，其中最复杂的是( )。 [单选题] * A. 集合 B. 线性结构 C. 树形结构 D. 图结构(正确答案) 关于栈和队列，下面叙述正确的是( )。 [单选题] * A. 函数的嵌套调用用队列来实现 B. 操作系统中进程调用用栈来实现
C. 程序递归的处理用队列来实现 D. 栈和队列是运算受限的线性表(正确答案) 设两个数据元素类型一致的栈共享一维数组空间data[max]成为双栈，两个栈的栈底分别设在数组两端，这两个栈的栈顶变量分别为top1和top2，且top2≥top1，则下列会发生"上溢"情况的是( )。 [单选题] * A. top1+1=top2;(正确答案) B. top1=top2; C. top2+1=top1; D. top1+top2=max; 设有一循环队列 SQ，现将数据 x 进行入队操作，语句为( )。 [单选题] * A. SQ.front=(SQ.front+1)%maxsize; B. SQ.rear=(SQ.rear+1)%maxsize; C. SQ.front=(SQ.front+1)%maxsize; SQ.data[SQ.front]=x; D. SQ.rear=(SQ.rear+1)%maxsize; SQ.data[SQ.rear]=x;(正确答案) 关于树的概念，下面叙述正确的是( )。 [单选题] * A. 树可以没有根节点(正确答案) B. 树中结点个数不为 0 C. 树中可以存在多个根节点 D. 若树中存在多个子树，则子树之间可以相交 邻接表的存储方法结合了( )。 [单选题] * A. 顺序存储与散列存储
试卷B 一、选择题（本题共20分,每题2分） 1．在数据结构中，从逻辑上可以把数据结构分成（ ） 。 A ．动态结构和静态结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧凑结构 D. 内部结构和外部结构 2. 下列程序段的时间复杂度是（ ） count=0; for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++; A.O(nlog2n) B.O(n) C.O(log2n) D.O(n2) 3. 以下描述错误的是：（ ） A. 线性表是n 个数据元素的有限非空集合。 B. 栈和队列都是操作受限的线性表。 C. 串（或字符串）是由零个或多个字符组成的有限序列。 D. 非空栈中的栈顶指针top 始终指向栈顶元素的下一个位置。 4. 若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列 Q （最大队列长度MAXSIZE ）为满队列的条件是( )。 A. Q.front=Q.rear B. Q.front!=Q.rear C. Q.front=(Q.rear+1) % MAXSIZE D. Q.front!=(Q.rear+1) % MAXSIZE 5. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。 A. 3 B. 4 C. 5 D. 6 6. 设矩阵A （如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）部分按行序存放在一维数组 B[n(n+1)/2]中，对下三角部分中任一元素 ai,j(i ≥j)，在一维数组 B 的下标位置k 的值是（ ）。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 0,01,0 1,11,01,1 1,1...............n n n n a a a A a a a ----⎡⎤ ⎢⎥⎢ ⎥ =⎢⎥ ⎢⎥ ⎣⎦ 7. 有一个有序表为｛5, 18，23, 33, 42, 54,56,78｝，当折半查找56时，经过（ ）次比较后查找成功。 A. 1 B. 2 C. 3 D. 8 8. 一组记录的排序关键字为（39，19，36，68，35，84），则利用快速排序方法进行正序排列时，以第一个记录为基准得到的一次划分结果为（ ）。 A. 35，36，19，39，68，84 B. 19，35，36，39，68，84 C. 35，19，36，39，84，68 D. 35，19，36，39，68，84 9.若对下图a 中的二叉树进行先序线索化，则结点x 的左、右线索指向的结点分别是（ ） A. e,c B. e,a C. d,c D. b,a