2010年数据结构期中考试试卷及答案

一、单项选择题(本题总分 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 ）。

1 / 72010年10月全国自考数据结构试题课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分） 1．数据的四种存储结构是(A )A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构2．若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是(C ) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表D.带头结点的单循环链表3．若带头结点的单链表的头指针为head ，则判断链表是否为空的条件是(B ) A.head=NULL B.head->next=NULL C.head!=NULLD.head->next!=head4．若元素的入栈顺序为1，2，3....，n ，如果第2个出栈的元素是n ，则输出的第i(1<=i<=n)个元素是(D )A.n-iB.n-i+lC.n-i+2D.无法确定5．串匹配算法的本质是(C )A.串复制B.串比较C.子串定位D.子串链接6．设有一个10阶的对称矩阵A ，采用行优先压缩存储方式，a 11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a 85的地址为(C ) A.13 B.18 C.33D.407．若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(B ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树D.树中非叶结点均只有右子树8．若根结点的层数为1，则具有n 个结点的二叉树的最大高度是(A )A.nB.2log n ⎢⎥⎣⎦C.2log n ⎢⎥⎣⎦+1D.n/2 9．在图G 中求两个结点之间的最短路径可以采用的算法是(A )2 / 7A.迪杰斯特拉（Dijkstra ）算法B.克鲁斯卡尔（Kruskal ）算法C.普里姆(Prim)算法D.广度优先遍历(BFS)算法10．下图G=(V,E)是一个带权连通图，G 的最小生成树的权为(D ) A.15 B.16 C.17 D.1811．在下图中，从顶点1出发进行深度优先遍历可得到的序列是(B ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 712．如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B ) A.不稳定的 B.稳定的 C.基于交换的D.基于选择的13．设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为(C ) A.1 B.2 C.3D.414．已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是(D)15．若需高效地查询多关键字文件，可以采用的文件组织方式为(D)A.顺序文件B.索引文件C.散列文件D.倒排文件二、填空题（本大题共10小题，每小题2分，共20分）16．下面程序段的时间复杂度为（O(n)）。

一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表的顺序存储表示优于链式存储表示。

( )3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )4、二维数组是其数组元素为线性表的线性表。

( )5、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

( )7、线性表中的每个结点最多只有一个前驱和一个后继。

（）8、线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

（）9、栈和队列逻辑上都是线性表。

（）10、单链表从任何一个结点出发，都能访问到所有结点（）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。

（）12、快速排序是排序算法中最快的一种。

（）13、多维数组是向量的推广。

（）14、一般树和二叉树的结点数目都可以为0。

（）15、直接选择排序是一种不稳定的排序方法。

（）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。

（）17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。

（）19、堆栈在数据中的存储原则是先进先出。

（）20、队列在数据中的存储原则是后进先出。

（）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）22、哈夫曼树一定是满二叉树。

（）23、程序是用计算机语言表述的算法。

（）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。

（）25、用一组地址连续的存储单元存放的元素一定构成线性表。

（）26、堆栈、队列和数组的逻辑结构都是线性表结构。

（）27、给定一组权值，可以唯一构造出一棵哈夫曼树。

（）28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

2010年春季学期计算机科学与技术、软件工程、网络工程专业《数据结构》期中考试卷面总分：100分答题时间：120分钟专业年级班级姓名学号说明：一、二题的答案必须写在以下答题卡上，写在别处不得分。

第二题答题卡：一、单项选择题（本大题共15小题，每小题2分，共30分答案写在答题卡上）1、算法分析的目的是（）A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档特点2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用链接存储，不必占用一片连续的存储单元。

C．线性表采用顺序存储，便于进行插入和删除操作。

D．线性表采用链接存储，便于插入和删除操作。

3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A．带头结点的双循环链表 B．双链表C．顺序表 D．单循环链表4、单链表中，增加一个头结点的目的是为了( ）。

A．使单链表至少有一个结点 B．标识表结点中首结点的位置C．方便运算的实现 D．说明单链表是线性表的链式存储5、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

A. 1，2，4，3B. 2，1，3，4C. 4，3，1，2D. 1，4，3，26、中缀表达式（A+B）*（C-D）/(E-F*G)的后缀表达式是_____；A. A+B*C-D/E-F*GB. AB+CD-*EFG*-/C. AB+C*D-E/F-G*D. ABCDEFG+*-/-*7、设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。

若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是A. 1B. 3C. 2D. 48、循环队列存储在数组A[0..m]中，则入队时的操作为( )。

A. rear=(rear+1) % (m-1)B. rear=(rear+1) % (m+1)C. rear=(rear+1) % mD. rear=rear+19、下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储10、串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？A. 可以顺序存储B. 数据元素是一个字符C. 数据元素可以是多个字符D. 可以链接存储11、对矩阵压缩存储是为了（）。

数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（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所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

杭州电子科技大学2010《数据结构》真题及解析一、是非题(每小题2分，共20分)1.线性表的顺序存储结构优于链式存储结构。

2.栈和队列也是线性表。

如果需要，可对它们中的任一元素进行操作。

3.非空广义表的表头和表尾都有可能是原子或广义表。

4.在二叉树的先序遍历序列中，任意-个结点均处在其孩子结点的前面。

5.通常，在二叉树的第i层上有2^i-1个结点。

6.二叉树按某种次序线索化后，任一结点均有指向其前驱和后继的线索指针。

6.赫夫曼树中的结点个数一定是奇数。

8.用邻接矩阵(数组表示法)存储一个图时，所需的存储空间大小与图的边数无关。

9.对于一棵m阶的B-树而言.树中每个结点至多有m个关键字，除根之外的所有非终端结点至少有┌m/2┐个关键字。

10.对于任何待排序序列来说，快速排序均快于冒泡排序。

二、选择题(每小题2分，共20分)1.递归过程可借助于_____转化为非递归过程。

A:线性表 B:队列 C:栈 D:数组2.循环队列用数组A[0..m-1]存放其元素值，设头尾游标分别为front(队头元素的位置)和rear(队尾元素的位置)，则当前队列中的元素个数是_______。

A: rear-front B: rear-front+1C: (rear-front+m)%m D: (rear-front+1+m)%m3.对广义表A=（（a, （6）），(c，（））,d）执行操作gettail(gethead(gettail （A）））的结果是:________。

A:（） B:(()) C:d D:(d)4.对二叉排序树______可得到有序序列。

A:按层遍历 B:前序遍历C:中序遍历 D：后序遍历5.在有n个结点的二叉树的二叉链表表示中，空指针数为________。

A:不定 B: n+1 C:n D：n-16.图示的三棵二叉树中_____为最优二叉树。

A: B: C:7.设无向图G=(V,E)和G=(V′,E′)，若G′是G的生成树，则下面不正确的说法是_________。

安徽大学2010—2011学年第2学期《 数据结构 》考试试卷（B 卷） （闭卷 时间120分钟）考场登记表序号一、填空题（每小题1.5分，共15分） 1．含有36个元素的有序表，进行二分查找时的判定树的深度为 6 。

2．在一个无向图中，所有顶点的度数之和等于所有边数的 2 倍。

3． 由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 44 。

4．由a ，b ，c 三个结点构成的二叉树，共有 5 种不同形态。

5．二维数组A[0‥5][5‥10]以行序为主序存储，每个元素占4个存储单元，且A[0][5]的存储地址是1000，则A[3][9]的地址是 1088 。

6．若串s=''soft ，则其子串个数是 11 。

7. 设循环队列的空间大小为M ，入队时修改队尾指针rear 的语句为 rear=(rear+1)%M 。

8．在顺序存储结构的线性表中，插入或删除一个数据元素大约需移动表中 一半 元素。

9．下列程序段的时间复杂度是 O(m*n) 。

for (i=0;i<n;i++) for (j=0;j<m;j++) A[i][j]+=5;10. 在数据结构中，与所使用的计算机无关的是数据的 逻辑 结构。

二、单项选择题（每小题2分，共20分）1. 数据结构可以用二元组来表示，它包括（ A ）集合D 和定义在D 上的（ C ）集合R 。

A 、数据元素B 、存储结构C 、元素之间的关系D 、逻辑结构2． 已知L 是一个不带头结点的单链表，p 指向其中的一个结点，选择合适的语句实现在院/系 年级 专业 姓名 学号答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------p结点的后面插入一个结点s的操作（B）。

数据结构期中试卷及答案解析考试说明考试说明：考察前五章小题，难度接近真题。

满分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。

一、选择题（每小题 1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。

A．表头 B．表尾 C．任意位置 D．指定位置2、下述哪一条是顺序存储结构的优点（2）。

A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示3、设有一个栈，元素的进栈次序为A, B, C, D, E，下列哪个是不可能的出栈序列（3）。

A．A, B, C, D, E B．B, C, D, E, AC．E, A, B, C, D D．E, D, C, B, A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至多有（4）个结点。

2k B．2k C．2k-1 D．2k+1A. 15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;6、下面程序段的时间复杂度为（6）。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A．O(m2) B．O(n2) C．O(m+n) D． O(m*n)7、非空的循环单链表head的尾结点指针p满足（7）。

A．p==NULL B．p== head C．p->next==head D．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。

A. 518B. 520C. 522D. 5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。

A．rear％n= = front B．（front+l）％n= = rearC．rear％n -1= = front D．(rear+l)％n= = front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。

2014-2015学年第二学期《数据结构与算法》期中考试学号：姓名：一、写语句1.设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。

2.设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作3. 设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入s结点的C语言描述语句。

4. 一线性表存储在带头结点的双向循环链表中，L为头指针。

如下算法：（1）说明该算法的功能。

（2）在空缺处填写相应的语句。

void unknown (BNODETP *L){ …p=L->next; q=p->next; r=q->next；while (q!=L){ while (p!=L) && (p->data>q->data) p=p->prior；q->prior->next=r；(1) ______；q->next=p->next；q->prior=p；(2) ______；(3) ______；q=r；p=q->prior；(4) ______；} }二、写算法1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：（要求用最少的时间和最小的空间）(1)确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）；(2) 在单链表将比正整数x小的数按递减次序排列；(3) 将正整数（比）x大的偶数从单链表中删除。

2. 设键盘输入n个英语单词，输入格式为n, w1, w2, …,wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：（1）如果单词重复出现，则只在链表上保留一个。

2010年数据结构考试模拟题型一、单选题（每题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 1B. 3 2 1C. 3 1 2D. 1 2 35. 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. 10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、填空题（每题6 分，共24分）1. 数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

数据结构2010年下学期 考试时间：100分钟 考试形式：闭卷（所有答案写在答题纸上，请在答题纸上注明班级、学号） 一、概念题（每题 2 分，共 24分） 1、从逻辑角度看，数据可归结为四类基本结构：集合、线性结构、 树状结构 和 图状结构 。

2、算法效率度量分析的两个基本指标是 时间复杂度 和 空间复杂度 。

前者是基于算法执行时间的度量，后者是基于算法所需存储空间的度量。

3、线性表顺序存储的特点是：表中相邻的元素a i 和a i+1所对应的存储地址 LOC （a i ）和LOC(a i+1)也是____相邻_____的。

设线性表a 的起始地址为LOC(a 1)，每个数组元素所占用的存储单元数为b ，则表中第i(1≤i ≤n)个元素a i 的存储起始地址LOC(a i )可用如下公式得到__ LOC(a i )_ = LOC(a 1)+(i-1)*b ______。

4、在线性表的存储结构中，顺序表是一个可 随机存取 存取的存储结构，单链表则是一个 顺序存取 存取的存储结构。

5、设单链表的结点数据类型定义和指针变量说明如下 #define DATATYPE2 char typedef struct node { DATATYPE2 data; struct node *next; } LINKLIST; LINKLIST *p,*q,*s; 在一个单链表中，已知q 所指向结点是p 所指向结点的直接前趋结点。

若欲在q 结点和p 结点之间插入一个s 所指向的结点，则可写 q->next=s;s->next=p 6、关于选用顺序表结构或链表结构，在考虑线性表的操作的时间性能时，若线性表上的操作主要是查找、读取而很少做插入和删除操作时，以采用 顺序 表结构为宜。

但是，若线性表需频繁地进行插入和删除操作时，则采用 链表 表结构为宜。

7、如果在待排序的序列中，存在有多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是 稳定 的；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是 不稳定 的。