数据结构图练习

数据结构练习题习题1 绪论单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。

①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。

①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。

）A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。

① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。

① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法!② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。

2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。

3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。

4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。

5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

一．填空题1、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___________；r=s; r->next=null;。

2、解决散列表冲突的两种方法是开放定址法和__________________。

3、设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。

4、模式串P=‘abaabcac’的next函数值序列为________。

5、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。

6、struct record{int key; int others;};int bisearch(struct record r[ ], int k){int low=0,mid,high=n-1;while(low<=high){________________________________;if(r[mid].key==k) return(mid+1);else if(____________) high=mid-1;else low=mid+1;}return(0);}7、设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。

8、设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。

9、for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。

10、设一组初始记录关键字序列为(48，37，64，96，75，12，26，50)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。

1．顺序存储结构中数据元素之间的逻辑关系是由（存储位置）表示的。

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

3. 执行下面程序段时，语句S的执行次数为(n+1)(n+2)/24 对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（顺序表）存储方式最节省时间。

5．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：n – i + 16．非空的单循环链表由头指针head指示，p 指针指向链尾结点的条件是（p->next==head）。

7．下列选项中，（可以随机访问表中的任意元素）是链表不具有的特点。

8.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（图）。

9．栈和队列的共同点是（只允许在端点处插入和删除元素）10．一个队列的入队序列是a,b,c,d，则该队列的出队序列是（a,b,c,d）。

11.带头结点的单链表h为空的判断条件是（h->next== NULL）。

12. 下面关于串的叙述中，哪一个是不正确的？（空串是由空格构成的串）13．判断一个最大容量为m的循环队列Q为空的条件是（Q->front==Q->rear）。

14．在一棵树中，每个节点最多有（1）前驱节点？15．已知完全二叉树的第7层有10个叶子结点，则整个二叉树中结点数为（73）。

16. 下面的说法中，不正确的是（稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储）17．在一棵深度为k的满二叉树中，结点总数为（2k-1）18．数组A中，每个元素的长度为3个字节，行下标从1到5，列下标从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（90）。

19. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有的顶点，则该图一定是（连通图）。

一、单项选择题1.逻辑关系是指数据元素间的（）A．类型 B．存储方式 C．结构 D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front= (front+1)%(m-1)C．front=(front-1)%m D．front=(fro nt+1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。

A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。

A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。

( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。

A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。

A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。

A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。

华东理工大学网络学院（专科）《数据结构》------第3章、第4章、第5章班级学号姓名成绩一、填空题（每空1分，共20分）1. 栈和队列是两种特殊的线性表，栈的特点是先进后出，表达式求值，栈的典型应用有和实现递归过程。

2. 在具有n个单元的循环队列中，队列满时共有n-1 个元素。

3. 若串的长度不能确定，可采用动态存储结构，为串值分配一个存储空间，同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置，称该结构为堆/堆结构。

4. 稀疏矩阵一种常用的压缩存储方法称为三元组表方式，即每个三元组表中的元素由、行、列、值、三部分组成。

5. 二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址是3260 。

6.进栈序列为a，b，c，则通过出栈和进栈操作可能得到的a，b，c的不同的排列序列有5 种。

7. 广义表((a,b),c,d)的表头是(a, b) ，表尾是(c,d) 。

8.已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是1168 。

9. 广义表((((a),b),c),d)的表头是(((a),b),c) ，表尾是(d) 。

10. 设s=’YOU ARE JUDGING IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8)；SubString(sub2,s,20,5)；StrCat(sub1,sub2); 则最后sub1的值为：’YOU ARE RIGHT’。

11. 假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：S->next=R->next ；R->next=S ；R=S 。

12.设有两个串p和q，求q在p中首次出现的位置的运算称作子串定位。

第7章图一、单选题01、在一个图中，所有顶点的度数之和等于图的边数的倍。

A．1/2 B．1C．2D．402、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A．1/2B．1 C．2 D．403、有8个结点的无向图最多有条边。

A．14 B．28 C．56 D．11204、有8个结点的无向连通图最少有条边。

A．5 B．6 C．7 D．805、有8个结点的有向完全图有条边。

A．14 B．28 C．56 D．11206、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A．栈 B．队列 C．树 D．图07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A．栈 B．队列 C．树 D．图08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。

A．O(n)B．O(e)C．O(n+e)D．O(n2)09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。

A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 210、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。

A．0 2 4 3 6 5 1 B．0 1 2 3 4 5 6C．0 4 2 3 1 5 6 D．0 1 3 4 2 5 611、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A．0 3 2 1 B．0 1 2 3 C．0 1 3 2 D．0 3 1 2 13、图的深度优先遍历类似于二叉树的。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历14、图的广度优先遍历类似于二叉树的。

数据结构练习题1⼀、单项选择题1.若⽤⼀个⼤⼩为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除⼀个元素，再加⼊两个元素后，rear和front的值分别为多少？( )A. 1和 5B. 2和4C. 4和2D. 5和1⼤⼩为6的数组：下标从0-5;从前⾯出队，从后⾯⼊队front(前⾯)=3rear(后⾯)=0当出队列中删除⼀个元素，也就是出队，即front+1:=4再插⼊两个元素，即rear+2= 2【注】循环队列中，由于⼊队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。

因此，⽆法通过条件front==rear来判别队列是"空"还是"满"。

2.循环队列A[0..m-1]存放其元素值，⽤front和rear分别表⽰队头和队尾，则当前队列中的元素数是( )。

A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front3.for（i=0；ifor（j=0；jA［i］［j］=i*j；上⾯算法的时间复杂度为( )A.O(m2)B.O(n2)C.O(m×n)D.O(m+n）4.设h是指向⾮空带表头结点的循环链表的头指针，p是辅助指针。

执⾏程序段p=h;while (p->next->next!=h)p=p->next;p->next=h;后（其中，p->next为p指向结点的指针域），则( )A. p->next指针指向链尾结点B. h指向链尾结点C. 删除链尾前⾯的结点D. 删除链尾结点5.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）A.head= =NULLB.head–>next= =NULLC.head!=NULLD.head–>next= =head6. 设顺序表有19个元素，第⼀个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )A.236B.239C.242D.2457. 若⼀棵⼆叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A ．9B ．11C ．15D ．不确定8. n 个结点的线索⼆叉树上含有的线索数为（）A ．2nB ．n －lC ．n ＋lD ．n9. 设有⼀个栈，按A 、B 、C 、D 的顺序进栈，则可能为出栈序列的是( )A.DCBAB.CDABC.DBACD.DCAB10. 归并排序中，归并的趟数是( )。

第一章绪论一．选择题1．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②的有限集合。

①A．算法B．数据元素C．数据操作D．逻辑结构②A．操作B．映象C．存储D．关系2．算法分析的目的是①，算法分析的两个主要方面是②。

①A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性②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．计算机算法指的是（1），它具备输入，输出和（2）等五个特性。

（1）A. 计算方法 B.排序方法C. 解决问题的有限运算序列D.调度方法（2）A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性9．以下关于数据的逻辑结构的叙述中正确的是（）。

A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构10．算法分析的主要任务是（）。

数据结构练习第六章树一、选择题1.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-13.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

A. 2m-1B. 2mC. 2m+1D. 4m4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A. BADCB. BCDAC. CDABD. CBDA5.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

A. 9B. 10C. 11D. 126．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

A. 2k-1 B .2k C. 2k-1 D. 2k-17．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。

A. N0=N1+1 B. N=Nl+N2C. N=N2+1 D. N=2N1+l8．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N=（）。

A. Nl +N2+……+Nm B. l+N2+2N3+3N4+……+(m-1)NmC. N2+2N3+3N4+……+(m-1)Nm D. 2Nl+3N2+……+(m+1)Nm9．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。

A. 20B. 30C. 40D. 4510．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。

A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子11．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。

A. 3B. 4C. 5D. 612．深度为k的完全二叉树中最少有（）个结点。

练习1.内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

2.叙述前序和中序遍历二叉树的步骤；一棵前序序列为1,2,3,4的二叉树,其中序序列可能是4,1,2,3吗?设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树。

3.设有一个关键码的输入序列{ 55, 31, 11, 37, 46, 73, 63 },(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。

若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。

(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度。

4.设散列表为HT[0..12],即表的大小为m=13。

现采用双散列法解决冲突。

散列函数和再散列函数分别为：H0(key)=key%13; 注：％是求余数运算（＝mod）H i=(H i-1+REV(key+1)%11+1)%13; i=1,2,3,…，m-1、其中，函数REV（x）表示颠倒10进制数x的各位，如REV(37)=73,REV(7)=7等。

若插入的关键码序列为{2,8,31,20,19,18,53,27}。

(1)试画出插入这8个关键码后的散列表。

(2)计算搜索成功的平均搜索长度ASL。

5.下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。

6.给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（1）归并排序每归并一次书写一个次序。

（2）快速排序每划分一次书写一个次序。

（3）堆排序先建成一个最大堆，然后每从堆顶取下一个元素后，将堆调整一次。

7.假设用于通讯的电文由5个字母组成，A B C D E F ，字母在电文中的出现频率分别为0.09，0.12，0.07，0.22，0.23，0.27，画出哈夫曼树，并写出各个字符的哈夫曼编码。

单元练习8一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）图可以没有边，但不能没有顶点。

（ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。

（ㄨ）（3）邻接表只能用于有向图的存储。

（√）（4）一个图的邻接矩阵表示是唯一的。

（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。

（ㄨ）（6）有向图不能进行广度优先遍历。

（√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。

（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。

（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。

（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。

二．填空题（1）图常用的存储方式有邻接矩阵和邻接表等。

（2）图的遍历有：深度优先搜和广度优先搜等方法。

（3）有n条边的无向图邻接矩阵中，1的个数是 _2n____。

（4）有向图的边也称为 _ 弧___ 。

（5）图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。

（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。

（7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为： O（n2）。

（8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为： O（n+e）。

（9）设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。

（10）设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。

（11）图的逆邻接表存储结构只适用于 __有向____图。

（12）n个顶点的完全无向图有 n(n-1)/2_ 条边。

（13）有向图的邻接表表示适于求顶点的出度。

（14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V i的入度。

第1章概论练习题一、单项选择题1.在数据结构中,从逻辑上可以把数据结构分为(B)A.紧凑结构与非紧凑结构B.线性结构与非线性结构C.内部结构与外部结构D.动态结构与静态结构2.若结点得存储地址与其关键字之间存在某种映射关系,则称这种存储结构为(D)A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构3.算法分析得两个主要方面就是(B)A.正确性与简明性B.时间复杂性与空间复杂性C.可读性与可维护性D.数据复杂性与程序复杂性4.线性表采用链式存储结构时,要求内存中可用存储单元地址(A)A.不一定连续得B.部分地址必须就是连续得C.必须就是连续得D.一定就是不连续得5.算法指得就是(C)A.计算机程序B.解决问题得计算方法C.解决问题得有限运算序列D.排序算法二、填空题6.数据结构一般包括逻辑结构、存储结构与数据运算三个方面得内容.7.数据得逻辑结构可分为线性结构、非线性结构两大类.8.数据得存储结构(物理结构)一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示.9.在选用求解一个问题得算法时,除了首先考虑算法就是“正确得”之外,还主要考虑执行算法所需要得时间、执行算法所需要得存储空间及算法应易于理解、易于编程、易于调试等三点。

10.设有一批数据元素,为了最快地存取某元素,宜用顺序结构存储,为了方便得插入一个元素,宜用链式结构存储.三、应用题设n为正整数,利用大“O”记号,写出下列各程序段得时间复杂度.11.for (i = 1; i <= n; i++){y = y + 1;for (j = 1; j <= 2 * n; j++)x = x + 1;}分析:语句“y = y + 1;”执行n次,语句“x = x + 1;”各执行次,故该程序段得时间复杂度为O().12.s = 0;while (n >= (s + 1) * (s + 1))s = s + 1;分析:语句“s = s + 1;”执行次,故该程序段得时间复杂度为O().13.x = 1;sum = 0;for (i = 0; i <= n; i++){x = x * i;sum = sum + x;}分析:语句“x = x * i”与“sum = sum + x;”各执行n次,故该程序段得时间复杂度为O(n).14.for (i = 1; i <= n; i++)if (3 * i <=n)for (j = 3 * i; j <= n; j++){x++;y = 3 * x + 2;}分析:语句“x++”与“y = 3 * x + 2;”各执行次,故该程序段得时间复杂度为O().15.for (i = 1; i <= n; i++)for (j = 1; j <= i; j++){x = x + 1;}分析:语句“x = x + 1;”执行次,故该程序段得时间复杂度为O().16.sum = 0; i = 0;while (i <= 100){sum = sum + i;i++;}分析:语句“sum = sum + i;”与“i++;”各执行100次,故该程序段得时间复杂度为O(1).17.x = 1;s = 0;for (i = 1; i <= n; i++){++x;s += x;}for (j = 1; j <= n; j++)for (k = 1; k <= n; k++){x++;s = s + x;}分析:语句“++x;”执行n次,语句“x++;”与“s = s + x;”各执行次,故该程序段得时间复杂度为O().第2章线性表练习题一、单项选择题1.在长度为n得顺序表得第i个位置上插入一个元素,元素得移动次数为(A)A. B. C. D.2.若一个顺序表中第一个元素得存储地址为1000,每个元素占4个地址单元,那么,第6个元素得存储地址应就是(A)A.1020B.1010C.1016D.10243.带头结点得单链表(以head为头指针)为空得判断条件就是(C)A.head != NULLB.head -> next == headC.head -> next == NULLD.head == NULL4.在单循环链表中,p指向表任一结点,判断表不就是访问结束得条件就是(B)A.p != NULLB.p != headC.p -> next != headD.p -> next != NULL5.在一个单链表中,已知q指向p所指向结点得前趋结点,若在p、q所指结点之间插入一个s所指向得新结点,则执行得操作就是(A)A.q -> next = s; s -> next = pB.p -> next = s; s -> next = qC.s -> next = p -> next; p -> next = sD.p -> next = s -> next; s -> next = p6.在一个单链表中,若删除p指向结点得后继结点,则执行得操作就是(A)A.q = p -> next; p -> next = p -> next -> next; free(q);B.p = p -> next; q = p -> next; p = q -> next; free(q);C.q = p -> next -> next; p = p -> next; free(q);D.p = p -> next -> next; q = p -> next; free(q);二、填空题7.在一个长度为n得顺序表中删除第i个元素,需要向前移动n- i个元素.8.在顺序表中插入或删除一个元素,需要平均移动表长得一半个元素,具体移动得元素个数与插入或删除得位置有关.9.顺序表中逻辑上相邻得元素在物理存储位置上一定相邻,链表结构中逻辑上相邻得元素在物理位置上不一定相邻.10.已知顺序表中一个元素得存储位置就是x,每个元素占c个字节,求其后继元素位置计算公式为x+ c,而已知单链表中某一结点由p指向,求此后继结点存储地址得操作为p -> next.11.在用p指针访问单链表时,判断不就是访问结束得条件就是p != NULL;在访问单循环链表时,判断不就是访问表结束得条件就是p != head.12.已知p指向双向链表得中间某个结点,从给定得操作语句中选择合适得填空.(1)在p结点后插入s结点得语句序列就是I、G、A、D.(2)在p结点前插入s结点得语句序列就是C、N、H、B.(3)删除p结点得直接后继结点得语句序列就是J、Q、E、M.(4)删除p结点得直接前趋结点得语句序列就是K、P、F、M.(5)删除p结点得语句序列就是O、R、L.A.p -> next = sB.p -> prior = sC.s -> next = pD.s -> prior = pE.p -> next = p -> next -> nextF.p -> prior = p -> prior -> priorG.p -> next -> prior = s H.p -> prior -> next = s I.s -> next = p -> nextJ.q = p -> next K.q = p -> prior L.free(p)M.free(q) N.s -> prior = p -> prior O.p -> prior -> next = p -> nextP.p -> prior -> prior -> next = p Q.p -> next -> next -> prior = p R.p -> next -> prior = p -> prior13.下面就是一个在带头结点得单链表head中删除所有数据域值为x得结点得算法,但不完善,请在相应得地方填上适当得语句,使之成为完整得算法.void DeleX(LinkList head, DataType x){LinkNode *p, *q, *s;P = head;q = p -> next;while (q != NULL)if (q -> data == x){s = q;q = q -> next;free(s);p -> next = q;}else{p = q;q = q -> next;}}三、算法设计题14.设有两个顺序表A与B,且都递增有序。

1.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为：【正确答案: C】A top不变B top=0C top--D top++得分：0.002.经过以下运算后，x的值是：InitStack (s); Push(s, a); Push(s, b); Pop(s, x); GetTop(s,x) 【正确答案: A】A aB 0C bD 1得分：0.003.元素A、B、C、D依次进栈后，栈顶元素是：【正确答案: B】A CB DC BD A得分：0.004.在带头节点的单链表L为空的判定条件是：【正确答案: A】A L->NEXT==NULLB L!=NULLC L->NEXT==LD L==NULL得分：0.005.将两个长度为n、m的递增有序表归并成一个有序顺序表，其最少的比较次数是（MIN表示取最小值）：【正确答案: B】A nB MIN(m, n)C mD 不确定得分：0.006.如果最常用的操作时取第i个元素及前驱元素，则下列存储方式最节省时间是：【正确答案: A】A 顺序表B 循环单链表C 双链表D 单链表得分：0.007.线性表的顺序存储结构和链式存储结构相比，优点是：【正确答案: D】A 所有的操作算法实现简单B 便于插入和删除C 节省存储空间D 便于随机存取得分：0.008.最不合适用做链队的不带头节点的链表是：【正确答案: B】A 以上都不合适B 只带队首节点指针的非循环单链表C 只带队尾节点指针的循环双链表D 只带队首节点指针的循环双链表得分：0.009.带表头结点的双循环链表L为空表的条件是：【正确答案: C】A L->prior==NULLB L==NULLC L->next==LD L->next->prior==NULL得分：0.0010.在某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素。