下载文档原格式
数据结构13级期中考试参考答案五邑大学试卷（期中参考答案）课程：数据结构学期： 2021 至 2021 学年度第 2 学期一、单项选择题（10小题，每小题2分，共20分）1．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n ，则第i个输出元素是（ D ）。
A．不确定 A．顺序表 A． 7B．n-i B．栈C．n-i-1 C．队列D．n-i+1 D．链表2．设计一个判别表达式中左右括号是否配对的算法，采用（ B ）数据结构最佳。
3．设有6个结点的无向图，该图至少应有（ C ）条边才能确保是一个连通图。
B. 6C. 5D. 4D．散列存取 D．O(nlog2n)4．线性表的顺序存储结构是一种（ A ）的存储结构。
A．随机存取 A．O(1)B．顺序存取 B．O(n)C．索引存取 C．O(n2)5．对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ C ）。
6．任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ A ）。
A．肯定不发生改变 C．不能确定B．肯定会发生改变 D．有时发生变化B．从源点到终点的最短路径 D．最短的回路7．关键路径是AOE网中（ A ）。
A．从源点到终点的最长路径 C．最长的回路 for(i=0; i B． O(n)C． O(log2n) C．树形结构 D． O(n2) 8．下列算法的时间复杂度是（ B ）。
9．下列四种基本的逻辑结构中，数据元素之间关系最弱的是（ A ）。
A．集合 B. 线性结构 D. 图状结构 10．在单链表中，若p所指结点不是尾结点，在p之后插入s所指结点的操作是（ B ）。
A．s->next=p; p->next=s C．s->next=p->next; p=s; 二、填空题(10小题，19个空，每空2分，共38分) 1．表示有100个顶点，133条边的无向图的邻接矩阵有（266）个非零矩阵元素。
一、单项选择题(本题总分 20分，每题 2分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母。
1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。
A.顺序表 B.链表 C.索引表 D.散列表采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是 按数据元素的关键字排序所得，它的数据元素是没有规律的2.在长度为 n 的顺序表的第 i(1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。
A.n -i+1B.n -iC.iD.i -1代入计算法，我们知道在 i=n+1 时不需要移动元素3.若一棵二叉树的先序遍历序列为 a,b,c ，则由 abc 三个结点构成的二叉树个数为( B ) 。
A.4B.5C.6D.74.三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 130，则元素 A[3][4][5]的存储地址为(B A.370B .368C .366) 。
D.372Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;5.高度为 h 的二叉树（仅含根结点的二叉树高度为 1）的结点最少是多少( D) 。
A. h+1B. 2hC. 2h －1D. h二叉树性质 26. 将两个各有 n 个元素的有序表归并成一个有序表，其最多的比较次数是( A. nB.n+1 C. 2n-1D. n-17. 已知一算术表达式的中缀形式为 A ＋B *C -D/E ，后缀形式为 ABC *+DE/-，其前缀形式为( C) 。
A )。
A. -+A*BC/DE C. -+*ABC/DEB. –A+B*CD/E D. –A+B*C/DE根据中缀和后缀表达式可画出表达树如下：- + /A* D EBC故前缀表达式为：-+A*BC/DE数据结构期中考试8．下面图示的顺序存储结构表示的二叉树是（ A ）。
数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（2010——2011学年度第⼀学期）命题教师：刘恒命题教师所在系：数计系课程名称：数据结构与算法考试专业：信计考试年级：09级⼀、单项选择题（每题2分，共30分，把正确答案填⼊表格中） 1、在数据结构中，从逻辑上可以把数据结构分成( C )。
A 、动态结构和静态结构B 、紧凑结构和⾮紧凑结构C 、线性结构和⾮线性结构D 、逻辑结构和存储结构 2、结构中的数据元素之间存在⼀个对多个的关系，称为(B )结构。
A 、线性 B 、树形 C 、图状 D 、⽹状 3、以下关于线性表的说法不正确的是(C )。
A 、线性表中的数据元素可以是数字、字符、记录等不同类型。
B 、线性表中包含的数据元素个数不是任意的。
C 、线性表中的每个结点都有且只有⼀个直接前驱和直接后继。
D 、存在这样的线性表：表中各结点都没有直接前驱和直接后继。
4、关于单链表的说法，请选出不正确的⼀项( C)。
A 、逻辑相邻、物理不⼀定相邻B 、不能随机存取C 、插⼊与删除需移动⼤量元素D 、表容量易于扩充 5、关于顺序表的说法，请选出不正确的⼀项(D )。
A 、逻辑相邻、物理相邻 B 、可实现随机存取 C 、存储空间使⽤紧凑 D 、表容量易于扩充6、设N 为正整数，试确定下列程序段中前置以记号@语句的频度为(A )。
x=91;y=100;while(y>0){@if(x>100){x-=10;y--;} else x++; } A 、1100 B 、 9100 C 、110 D 、 9107、在顺序表中删除⼀个元素，平均需要移动( C)元素，设表长为n 。
A、n/2-1 B 、n/2+1C 、n/2D 、(n+1)/28、对单链表执⾏下列程序段，请选出正确的⼀项( A)。
T=P;While(T->next!=NULL ){T —>data=T —>data*2;T=T —>next;} A 、R->data=4 B 、R->data=8C 、H->data=4D 、Q->data=79、若⼀个栈的输⼊序列是1，2，3，┅，n ，输出序列的第⼀个元素是n,则第k 个输出元素是( C)。
《数据结构》期中测试班级：姓名：学号：一、填空题：1、在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。
数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。
2、算法的五个重要特性是有穷性、确定性、可行性、输入和输出。
3、一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。
在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。
顺序表中逻辑上相邻的元素的物理位置相邻。
单链表中逻辑上相邻的元素的物理位置不一定相邻。
单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。
在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。
4、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。
在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。
给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。
5、已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
在p所指结点后插入s所指结点：4、1。
在p所指结点前插入s所指结点：7、11、8、4、1。
在表首插入s所指结点：5、12。
在表尾插入s所指结点：11、9、1、6。
1)p->next=s;2)p->next=p->next->next;3)p->next=s->next;4)s->next=p->next;5)s->next=L;6)s->next=NULL;7)q=p;8)while(p->next!=q) p=p->next;9)while(p->next!=NULL) p=p->next;10)p=q;11)p=L;12)L=s;13)L=p;6、已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
福建师范大学数学与计算机科学学院
2009--2010学年度上学期08电信
《数据结构》期中试题
试卷类别：闭卷考试时间：90分钟
倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天的颜色。
周遭流岚升腾，没露出那真实的面孔。
面对那流转的薄雾，我会幻想，那里有一个世外桃源。
在天阶夜色凉如水的夏夜，我会静静地，静静地，等待一场流星雨的来临…
许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流…
秋日里，阳光并不刺眼，天空是一碧如洗的蓝，点缀着飘逸的流云。
偶尔，一片飞舞的落叶，会飘到我的窗前。
斑驳的印迹里，携刻着深秋的颜色。
在一个落雪的晨，这纷纷扬扬的雪，飘落着一如千年前的洁白。
窗外，是未被污染的银白色世界。
我会去迎接，这人间的圣洁。
在这流转的岁月里，有着流转的四季，还有一颗流转的心，亘古不变的心。
计05期中数据结构试题及答案数据结构期中试题一. 单项选择题（每项选择2分，共48分）1．在数据结构中，从逻辑上可以把数据结构分成___C____。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构2．线性表是 A 。
(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。
3．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的 B 个元素。
(A) n/2 (B) n+1/2 (C) n -1/2 (D) n 4．用链表表示线性表的优点是 C 。
(A)便于随机存取(B)花费的存储空间较顺序存储少 (C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用 C 存储方式最节省运算时间。
(A)单链表 (B)双链表 (C)带尾指针的单循环链表 (D)双循环链表6线性表的顺序存储结构是一种_A____的存储结构，线性表的链式存储结构是一种_____的存储结构。
A．随机存取 B．顺序存取 C．索引存取 D．散列存取7、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用B 存储方式最节省运算时间。
(A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表8．算法分析的目的是___C___，算法分析的两个主要方面是__A____。
①A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进D．分析算法的易懂性和文档性②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性9、栈的特点是① B ，栈和队列都是 C ② 。
①、 A、先进先出 B、后进先出②、 A、顺序存储的线性结构C、操作受限的线性结构C、进优于出D、出优于进B、链式存储的线性结构 D、操作受限的非线性结构10、若进队列的序列为1,2,3,4，则 D 是一个出队序列。
试卷编号命题人：审核人：试卷分类（A卷或B卷）五邑大学试卷参考答案及评分标准学期：至学年度第学期课程：数据结构课程代号：006A1060使用班级：一、单项选择题(15小题，每小题1分，共15分)1．顺序存储结构中数据元素之间的逻辑关系是由（ C ）表示的。
A．线性结构B．非线性结构C．存储位置D．指针2．用数组r存储静态链表，结点的next域指向后继，工作指针j 指向链表中某结点，则j 后移的操作语句为（ A ）。
A．j=r[j].next; B．j=j+1; C．j=j->next; D．j=r[j]->next;3．若一个栈的输入序列是1,2,3，…，n，其输出序列是p1,p2,…，p n，若p1=3，则p2的值（ C ）。
A．一定是2 B．一定是1 C．不可能是1 D．以上都不对4．设有两个字符串p和q，求q在p中首次出现的位置的运算称作（ B ）。
A．连接B．模式匹配C．求子串D．求串长5．下述编码中（ B ）不是前缀编码。
A．(00,01,10,11) B．(0,1,00,11) C．(0,10,110,111) D．(1,01,000,001) 6．设森林中有4棵树，树中结点的个数依次为n1,n2,n3和n4，则把森林转换成二叉树后，其根结点的右子树上有（ D ）结点。
A．n1-1 B．n1C．n1+n2+n3D．n2+n3+n47．设有如下图所示的AOV网，不可能的拓扑排序结果是（ C ）。
A．C1 C2 C3 C4 C5 C6 C7B．C2 C1 C3 C4 C5 C6 C7C．C1 C2 C6 C4 C3 C5 C7D．C1 C2 C4 C6 C3 C5 C78．设哈夫曼编码的长度不超过4，若已经对两个字符编码为1 和01，则最多还可以为（ C ）个字符编码。
A．2 B．3 C．4 D．59．对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ D ）。
数据结构期中试卷及答案解析考试说明考试说明：考察前五章小题，难度接近真题。
满分100分，共20道选择题，每题5分。
请在60分钟内完成。
C T(n)=n3+5000nD T(n)=2nlogn-1000n参考答案：C本题考察时间复杂度，多个项相加时，只保留最高阶项由于巴啦啦能量——“常<对<幂<指<阶”，因此T(n)=logn+5000n=O(n)T(n)=n2-8000n=O(n2)T(n)=n3+5000n=O(n3)T(n)=2nlogn-1000n=O(nlogn)所以O(n3)复杂度最大，选C。
3.下列叙述中正确的是（）①线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比②线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关③线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比A. 仅①B. 仅②C. 仅③D. ①②③参考答案：A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比。
线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A. 单链表B. 双向链表C. 单循环链表D. 顺序表参考答案：D注意到，题目要求存取第i个元素及其前驱和后继，ABC三个选项找到第i个元素的时间复杂度均为O(n)，而D选项对于这3个位置的存取的时间复杂度均为O(1)，故选D。
5.静态链表中next域表示的是（）A 下一个元素的地址B 下一个元素的值C 当前元素的值D 下一个元素在数组中的位置参考答案：D静态链表一般保存在数组中，它和链表最大的区别是静态链表占用一段固定的区间，所以next域只需要表示下一个元素在数组中的下标即可而不是表示下一个元素的地址，选D。
6.对于不带头结点的链栈L（next域表示该结点下一个元素），top指针指向栈顶元素（栈顶在链头方向），则x结点进栈操作为A top->next=x;top=x;B top=x;top-next=x;C top=x;x->next=top;D x->next=top;top=x;参考答案：D本题考察链栈的操作x入栈之后x下一个元素为原来的top，所以先把x->next=top，然后更新top，栈顶元素指向x。
