下载文档原格式
数据结构练习题习题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. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
第九章查找9.3 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：判定树应当描述每次查找的位置：9.9已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
解：9.19解：H(22)=(3×22) mod 11=0 H(41)=(3×41) mod 11=2 H(53)=(3×53) mod 11=5 H(46)=(3×46) mod 11=6H(30)=(3×30) mod 11=2 冲突d1=(7×30) mod 10+1=1 H1（30）=(2+1)/11=3 H(13)=(3×13) mod 11=6 冲突d1=(7×13) mod 10+1=2 H1（13）=(6+2)/11=8 H(01)=(3×01) mod 11=3冲突d1=(7×1) mod 10+1=8 H1（01）=(3+8)/11=0冲突d2=2*（(7×1) mod 10+1）=16 H2（01）=（3+16）/11=8冲突d3=3*（(7×1) mod 10+1）=24 H3（01）=（3+24）/11=5冲突d4=4*（(7×1) mod 10+1）=32 H4（01）=（3+32）/11=2冲突d5=5*（(7×1) mod 10+1）=40 H5（01）=（3+40）/11=10H(67)=(3×67) mod 11=3冲突d1=(7×67) mod 10+1=10 H1（67）=（3+10）/11=2冲突d2=2*((7×67) mod 10+1)=20 H2（67）=（3+20）/11=1哈希表：ASL=(1+1+1+1+2+2+6+3)/8=17/8X。
数据结构1.鼓励独立完成作业，严惩抄袭[2.4.1] 在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n)时，需要依次前移______个元素。
A. A. n-i正确答案：A2.[2.4.2] 在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为：C. C. (n+1)/2正确答案：C3.[2.4.3] 在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行D. D. p->next = q->next ; q->next = p;正确答案：D4.[2.4.4] 在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行C. C. p = q->next ; q->next = p->next;正确答案：C5.[3.5.1] 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的________A. A. 行号正确答案：A6.[3.5.2] 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_______。
B. B. O(n)正确答案：B7.[6.2.1] 下列关键字序列中，________是堆。
D. D. 16, 23, 53, 31, 94, 72正确答案：D8.[6.2.2] 堆的形状是一棵____________。
C. C. 完全二叉树正确答案：C计算题.doc10.[2.1] 线性表的两种存储结构顺序表和链表中：（1）两种存储表示各有哪些主要优缺点?（2）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。
在此情况下，应选用哪种存储结构？给予解释？（3）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？给予解释？正确答案：（1）顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。
东师《数据结构（高起专）》15秋在线作业1一、单选题（共20 道试题，共60 分。
）V 1. 在k叉树中，度为0的结点称为( )。
A. 根B. 叶C. 祖先D. 子孙满分：3 分2. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是( )。
A. UB. VC. XD. Y满分：3 分3. 顺序表中逻辑上相邻的结点其物理位置也( )。
A. 一定相邻B. 不必相邻C. 按某种规律排列D. 无要求满分：3 分4. head指向的非空的单循环链表的尾结点(由p所指向)满足( )。
A. p->next = = NULLB. p = = NULLC. p->next = = headD. p = = head满分：3 分5. 若X是中序线索二叉树中一个有左子女的结点，且X不为根，则X的中序前驱为( )。
A. X的双亲B. X的右子树中最左下的结点C. X的左子树中最右下的结点D. X的左子树中最右下的叶结点满分：3 分6. 在线索二叉树中，p所指结点没有右子树的充要条件是( )。
A. p->rchild = = NULLB. p->rtag = = 1C. p->rtag = = 1且p->rchild = = NULLD. p->rtag = = 0满分：3 分7. 一个算法应该是（）。
A. 程序B. 问题求解步骤的描述C. 要满足五个基本特性D. A和C满分：3 分8. 将一棵有100个结点的完全二叉树从上到下、从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右子女编号为( )。
A. 48B. 50C. 98D. 99满分：3 分9. 在一个单链表中，在p所指结点之后插入s所指结点，则执行( )。
A. s->next = p; p->next = s;B. s->next = p->next; p->next = s;C. s->next = p->next; p = s;D. p->next = s; s->next = p->next;满分：3 分10. 在下面的叙述中，正确的是( )。
兰州大学《数据结构》15秋在线作业1满分答案一、单选题（共 10 道试题，共 50 分。
）1. 数据结构是一门研究非数值的程序设计问题中计算机的? 以及它们之间的关系和运算等的学科A. 操作对象B. 计算方法C. 逻辑存储D. 物理存储正确答案：A2. 一个二叉树的第i层至多有____ 个节点A. 2^iB. 2^i-1C. 2^(i-1)D. 2^(i-1)-1正确答案：C3. 单链表的结点包含____和_____A. 结点域，符号域B. 数据域，符号域C. 结点域，指针域D. 数据域，指针域正确答案：D4. 设s =“I AM A STUDENT”,则字符串的长度 Length(s) ＝？A. 11B. 12C. 14D. 15正确答案：C5. 若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____A. n2+1B. n2-1C. n2+2D. n2-2正确答案：A6. 常对数组进行的两种基本操作是A. 建立与删除B. 索引与修改C. 查找与修改D. 查找与索引正确答案：C7. for (j=1## j<=n## ++j) s=s+1##A. O(n)B. O(1)C. O(n^2)D. O(n^3)正确答案：A8. 图的深度优先遍历算法类似于二叉树的____A. 先序遍历B. 中序遍历C. 后序遍历D. 层次遍历正确答案：A9. 线性表的顺序存储结构是一种?的存储结构A. 随机存取B. 顺序存取C. 索引存取D. 散列存取正确答案：A10. 折半查找适用于：_____A. 采用顺序存储结构的有序表B. 采用链式存储结构的有序表C. 采用顺序存储结构的无序表D. 采用链式存储结构的无序表正确答案：A《数据结构》15秋在线作业1二、判断题（共 10 道试题，共 50 分。
）1. 算法和程序没有区别A. 错误B. 正确正确答案：A2. 栈是限定在表尾进行插入或删除操作的线性表A. 错误B. 正确正确答案：B3. 对于哈希函数，冲突只能尽可能得少，不可能完全避免A. 错误B. 正确正确答案：B4. 数据元素是数据的最小单位A. 错误B. 正确正确答案：A5. 哈夫曼树是带权路径长度最短的树A. 错误B. 正确正确答案：B6. 平衡二叉树的平衡因子只可能是-1、0、1A. 错误B. 正确正确答案：B7. 一个广义表的表头总是一个广义表A. 错误B. 正确正确答案：A8. 数据的逻辑结构是指各数据元素之间的逻辑关系A. 错误B. 正确正确答案：B9. 线性结构的链式存储结构在插入或删除某一元素时，不需要移动大量元素A. 错误B. 正确正确答案：B10. 森林的先序遍历与其对应的二叉树的中序遍历对应A. 错误B. 正确正确答案：A。
2015年秋季学期《数据结构》课程作业一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。
（每空1分，共30分）1.鼓励独立完成作业，严惩抄袭！数据的逻辑结构被形式地定义为B=(K,R),其中K是 ____C__的有限集合，R是K上的___H___的有限集合。
（第一章）a 存储b 数据操作c数据元素d操作e逻辑结构 f 映象 g算法h关系2.以下关于算法的说法不正确的是____B _________。
（第一章）a 一个算法应包含有限个步骤b算法越简单越好c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之d算法中的每个步骤都能在有限时间内完成3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是______B________。
（第一章）a 线性结构b 树型结构c 物理结构d 图型结构4.下面程序段的时间复杂度为___C___（第一章）int sum=0;for(i=0; i<m;i++)for(j=i;j<n;j++)s++;a. O(m+n)b. O(n*n)c. O(m*n)d. O(m*logn)5. 下列有关线性表的叙述中，正确的是____A____。
（第二章）a 一个线性表是 n 个数据元素的有限序列b 线性表中任何一个元素有且仅有一个直接前驱c 线性表中任何一个元素有且仅有一个直接后继d 以上说法都不正确6.在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为___B___（第二章）a．n b．n/2 c．(n+1)/2 d．(n-1)/27.链表不具备的特点是______D___。
《数据结构》形成性考核册第1次作业参考答案第一章绪论一、填空题1、数据操作2、集合结构线性结构树型结构图形结构3、引用类型4、1：1 1：n n：m5、不对6、多个7、O（m*n）8、时间复杂度空间复杂度9、顺序链接索引散列10、O（n2）11、O（n）12、O（n）O（m*n）二、选择题1~8：DBABADDD三、应用题（1）功能：判断n是否是一个素数，若是则返回数值1，否则返回0。
时间复杂度：O（n）。
（2）功能：计算S=1！+2！+…+n!的值。
时间复杂度：O（n）。
（3）功能：计算S=1！+2！+…+n!的值。
时间复杂度：O（n2）。
（4）求出满足不等式1+2+…+i≥n的最小i值。
O（n）。
第二章线性表四、填空题1、A[P-1]2、1083、前驱后继4、最后一个表头5、p->next=q->nextq->next=p6、HL->next=NULLHL->next=HL7、P->next8、Q->next9、P->next s10、从前向后前移n-i11、O（1）O（n）12、（n+1）/213、O（n）O（1）14、A[P].next15、a[j].next=a[i].nexta[i].next=j16、数据值指针五、选择题1~5：BDDBC六、应用题1、（1）、（79，62，34，57，26，48）（2）、（26，34，48，57，62，79）（3）、（48，56，57，62，79，34）（4）、（56，57，79，34）（5）、（26，34，39，48，57，62）2、（1）将类型为List的线性表L中第i个元素移至表尾位置的算法，L中的元素类型为ElemType，假定不需要对i的值进行有效性检查。
void move (List& L, int i){ElemType x=L.list[ i-1];for(int j=i; j<L.size; j++)L.list[ j-1]=L.list[ j ];L.list[L.size-1]=x;}·将线性表L中的第i个元素移入表头的算法与上类似。
2015年秋季学期《数据结构》课程作业一. 单选题，每空有一个正确选择，请将正确的选择填在题号前边。
（每空1分，共30分）1.鼓励独立完成作业，严惩抄袭！数据的逻辑结构被形式地定义为B=(K,R),其中K是 ____C__的有限集合，R是K上的___H___的有限集合。
（第一章）a 存储b 数据操作c数据元素d操作e逻辑结构 f 映象 g算法h关系2.以下关于算法的说法不正确的是____B _________。
（第一章）a 一个算法应包含有限个步骤b算法越简单越好c算法中的所有操作都可以通过已经实现的基本操作运算有限次实现之d算法中的每个步骤都能在有限时间内完成3．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是______B________。
（第一章）a 线性结构b 树型结构c 物理结构d 图型结构4.下面程序段的时间复杂度为___C___（第一章）int sum=0;for(i=0; i<m;i++)for(j=i;j<n;j++)s++;a. O(m+n)b. O(n*n)c. O(m*n)d. O(m*logn)5. 下列有关线性表的叙述中，正确的是____A____。
（第二章）a 一个线性表是 n 个数据元素的有限序列b 线性表中任何一个元素有且仅有一个直接前驱c 线性表中任何一个元素有且仅有一个直接后继d 以上说法都不正确6.在含有n个结点的顺序存储的线性表中，在任一位置插入一个结点所需移动结点的平均次数为___B___（第二章）a．n b．n/2 c．(n+1)/2 d．(n-1)/27.链表不具备的特点是______D___。
（第二章）a不必事先估计存储空间 b 插入删除不需要移动元素c 可顺序访问任一结点d 所需空间与其长度无关8.带附加头结点的双循环链表L为空表的条件是_______C_____。
（第二章）a L==NULLb L->next==NULLc L->prior==Ld L->prior==NULL9.设广义表L=（（a,b,c））,则L的长度与深度分别为___D_________。
（第三章）a 1和1b 1和3c 2和3d 1和210. 若栈采用链式存储结构,则下面的说法中正确的是____A____（第四章）a.不需要判断栈满但需要判断栈是否为空b.需要判断栈是否栈空与栈满c.需要判断栈满但不需要判断栈空d.栈满栈空都不需要判断11. 在一个链栈中，已知s为栈顶指针（直接指向栈顶元素结点，无头结点），t为栈底指针，直接指向栈底元素，则插入r结点的操作为_____B_______。
（第四章）a t->next=r;t=r;b r->next=s;s=r;c s->next=r;s=r;d r->next=t;12.一个栈的输入序列为1，2，3，4，5，6下面哪一个序列不可能是这个栈的输出序列___B___（第四章）a. 1, 2, 3, 4, 5, 6b. 3, 2, 6, 4, 5, 1c. 2, 4, 6, 5, 3, 1d. 6, 5, 4, 3, 2, 113. 循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_____A_______。
（第四章）a (rear-front+m)%mb rear-front+1c rear-front-1d rear-front14.栈和队列的共同特点是______A____。
（第四章）a.只允许在端点处插入和删除元素b.都是先进后出c.都是先进先出d.没有共同点15.中缀表达式(A+B)*D+E/(F+A*D)+C的后缀形式是__D____（第四章）a．AB+D*E/FA+*DC+ b．ABD*+EFAD*+/C+c．ABDEFADC+*+/+*+ d．AB+D*EFAD*+/+C+16.如下图所示的4棵二叉树，____C_____不是完全二叉树。
（第五章）17. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为_____C_______。
（第五章）a 9b 10c 11d 1218. 深度为6(根的层次为1)的二叉树至多有____B___结点（第五章）a.64b.63c.31d.3219.二叉树的第k层的结点数最多为________D____。
（第五章）a. 2k-1b. 2K+1c. 2K-1d. 2k-120.如果一棵二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是____B___。
（第五章）a 空或只有一个结点b 高度等于其结点数c 任一结点无右孩子d 任一结点无左孩子21. 树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
结论_______A__是正确的。
（第五章）a.树的先根遍历序列与其对应的二叉树的先序遍历序列相同b.树的后根遍历序列与其对应的二叉树的先序遍历序列相同c.树的先根遍历序列与其对应的二叉树的中序遍历序列相同d.以上都不对22.根据使用频率为5个字符设计的哈夫曼编码不可能是______B______。
（第六章）a 111，110，10，01，00b 000，001，010，011，01c 001，000，01，11，10d 100，111，110，101，023. 下列数据结构中,不属于二叉树的是______D______（第六章）a. 堆b. 哈夫曼树c. 线索二叉树d. B树24.采用邻接表存储的图的广度优先遍历算法类似于二叉树的_____D_____。
（第七章）a 先序遍历b 中序遍历c 后序遍历d 层次遍历25.对用邻接表表示的图进行深度优先遍历时，通常是借助___A______来实现算法。
（第七章）a 栈b 队列c 树d 图26. 在一个图中，所有顶点的度数之和等于图的边数的____C_____倍。
（第七章）a. 1/2b. 1c. 2d. 427.对线性表进行二分查找，要求线性表必须_______B_____。
（第九章）a 以顺序方式存储b 以顺序方式存储，且结点按关键字有序排序c 以链接方式存储d 结点按关键字有序排序，存储方式无所谓28.排序方法中，每次从未排序序列中查找值最小的元素放到已排序序列（初始时为空）的末尾，该排序方法称为_______C_____。
（第十章）a 希尔排序b 冒泡排序c选择排序 d 插入排序29.下列四种排序中，_______C_____的空间复杂度最大。
（第十章）a. 插入排序b. 冒泡排序c. 归并排序d. 快速排序二. 填空题，请将正确答案填在____上。
（每空1分，共30分）1.数据结构分为____逻辑结构____和物理结构两种结构。
（第一章）2.线性结构中元素之间存在一对一关系，而树形结构中元素之间存在__一对多___关系，图形结构中元素之间存在多对多关系。
（第一章）n+4n-7)/(5n),则该算法的时间复3.一个算法的最基本的原操作执行次数为(3n2+2nlog2杂度为____ O(n)_____。
（第一章）4.链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑关系通过___指针_______间接地反映。
（第二章）5.向一个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动_____N-i+1_______个元素。
（第二章）6.当线性表的元素总数不固定，且很少随机存取表中元素，但插入和删除操作较多时，应采用_____链式_____存储结构。
（第二章）7.在单链表中，要删除某一指定的结点，必须找到该结点的______前驱______结点。
（第二章）8.删除单链表中结点p所指向的下一个结点（假设不为空）时，应执行q=____P->next__,p->next=__ q->next ____和___ delete q____的操作。
（第二章）9.设广义表L=（（a，（b,c,d）））,则L的长度为_____1___，深度为_____3____。
（第三章）10.队列的特点是先进先出，与之对应，栈的特点是___后进先出_________。
（第四章）11.在栈顶进行插入删除一个元素的时间复杂度是___ O(1)_____。
（第四章）12.后缀算式9 2 3 +- 10 2 / -的值为__-1____。
（第四章）13.一个环形队列中共有MaxSize个单元，那么队满时共有__ MaxSize – 1____个元素。
（第四章）14.设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a5,a4,a8,a7,a6,a2,a1，则栈S的容量至少应该是______5______。
（第四章）15.一棵高度为6的完全二叉树至少有____32____个结点，最多有___63___个结点。
（第五章）16.如果一个完全二叉树的叶子结点个数为n，则这棵二叉树的总结点数为__2n或2n-1___。
（第五章）17.设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为______CABD____。
（第五章）18.已知一个有向图的邻接矩阵表示，计算第i个结点的度的方法是__求矩形第i行非零元素之和__。
（第七章）1、19.一个图的三种存储方法中，__________邻接矩阵，邻接表和边集数组____________表示法是不唯一的。
（第七章）2、20.一个有n个顶点的无向连通图最少有__n-1_条边，最多___ n(n-1)/2___条边。
（第七章）21.设一个连通图G中有n个顶点e条边，则其最小生成树上有_____n-1___条边。
（第八章）22.外排序是指在排序前后，数据在___外存____上，排序时数据调入内存进行的排序方法。
（第十章）23.在选择排序、冒泡排序、归并排序中，_____选择____排序是不稳定的。
（第十章）三. 简答题。
（每小题4分，共40分）1.简述顺序表和链表存储方式的特点。
（第二章）顺序表的优点势可以随机访问数据元素；缺点是大小固定，不利于增减结点（增减操作需要移动元素）。
链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）。
