数据结构习题(题型版)

三、填空题1数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示。2. 对于给定的 n 个元素,可以构造出的逻辑结构有 线性结构 、树形结构、图形结构、集合四种。 3数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。4一个数据结构在计算机中表示（又称映像）称为存储结构。 5抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 6数据结构中评价算法的两个重要指标是 时间复杂度 和 空间复杂度 。7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互关系，并对与这种结构定义相应的操作，设计出相应的算法。 8 一个算法具有5个特性: 有穷性 、 确定性 、 可行性 ，有零个或多个输入、有一个或多个输出。11.下面程序段中带下划线的语句的执行次数的数量级是（log2n）i=1； WHILE in DO i=i*2; 12. 下面程序段中带下划线的语句的执行次数的数量级是(nlog2n )。i=1；while (in) for(i=1;i1) sum=1； for (i=0；sumn；i+) sum+=1； 8对于一个数据结构，一般包括哪三个方面的讨论？逻辑结构、存储结构、操作（运算）4在一个长度为 n 的顺序表中第 i个元素（1=inext-next=L 16. 在单链表 L 中，指针 p 所指结点有后继结点的条件是： p-next!=null 17.带头结点的双循环链表 L 为空表的条件是： L-next=L & L-prior=L 。 18. 在单链表 p 结点之后插入 s 结点的操作是： s-next=p-next;p-next=s; 。 1栈是 操作受限 的线性表，其运算遵循 后进先出 的原则。 2 栈 是限定仅在表尾进行插入或删除操作的线性表。3. 一个栈的输入序列是：1，2，3 则不可能的栈输出序列是 312 。4. 设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为 1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是 23 ，而栈顶指针值是 100C H。设栈为顺序栈，每个元素占 4 个字节。 5. 当两个栈共享一存储区时，栈利用一维数组 stack(1,n)表示，两栈顶指针为 top1与 top2，则当栈1 空时，top1为 0 ，栈2 空时 ，top2为 n+1 ，栈满时为 top1+1=top2 。 6两个栈共享空间时栈满的条件 两栈顶指针值相减的绝对值为1（或两栈顶指针相邻） 。 8. 多个栈共存时，最好用 链式存储结构 作为存储结构。 9用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S和X 的操作串为 SSSS 。 10. 顺序栈用 data1.n存储数据，栈顶指针是 top,则值为 x 的元素入栈的操作是 data+top=x；。 11表达式23+(12*3-2)/4+34*5/7)+108/9 的后缀表达式是 23.12.3*2-4/34.5*7/+108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数）12. 循环队列的引入，目的是为了克服 假溢出时大量移动数据元素 。 14 队列 又称作先进先出表。 15. 队列的特点是先进先出 。 16队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是 先进先出 。 17. 已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是 s=(LinkedList)malloc(sizeof(LNode)； s-data=x;s-next=r-next；r-next=s；r=s； 。 18区分循环队列的满与空，只有两种方法，它们是 牺牲一个存储单元 和 设标记 。 21表达式求值是 栈 应用的一个典型例子。 22循环队列用数组 A0.m-1存放其元素值，已知其头尾指针分别是 front 和 rear ，则当前队列的元素个数是（rear-front+m）% m 。 23设 Q0.N-1为循环队列，其头、尾指针分别为 P 和 R，则队 Q 中当前所含元素个数为（R-P+N）% N。1空格串是指 由空格字符（ASCII值32）所组成的字符串 ，其长度等于 空格个数 。2组成串的数据元素只能是 字符 。 3一个字符串中 任意个连续的字符组成的子序列 称为该串的子串 。4INDEX（DATASTRUCTURE，STR）= 5 。8设 T 和 P 是两个给定的串，在 T 中寻找等于 P 的子串的过程称为 模式匹配 ，又称P 为 模式串 。 9串是一种特殊的线性表，其特殊性表现在 其数据元素都是字符 ；串的两种最基本的存储方式是 顺序存储 、 链式存储 ；两个串相等的充分必要条件是 串的长度相等且两串中对应位置的字符也相等 。10两个字符串相等的充分必要条件是 两串的长度相等且两串中对应位置的字符也相等 。11知U=xyxyxyxxyxy；t=xxy；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1）；ASSIGN（m，ww）求REPLACE（S，V，m）=xyxyxywwy。1. 数组的存储结构采用 顺序存储结构 存储方式。 3. 设数组 a1.50,1.80的基地址为2000，每个元素占 2 个存储单元，若以行序为主序顺序存储，则元素a45,68的存储地址为 9174 ;若以列序为主序顺序存储，则元素 a45,68的存储地址为 8788 。4. 将整型数组 A1.8，1.8按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 A7，3的地址是： 1100 。 6. 设有二维数组 A0.9,0.19,其每个元素占两个字节，第一个元素的存储地址为 100，若按列优先顺序存储，则元素 A6,6存储地址为 232 。 11设n 行n 列的下三角矩阵 A 已压缩到一维数组 B1.n*（n+1）/2中，若按行为主序存储，则 Ai,j对应的 B 中存储位置为 i(i-1)/2+j (1=i,j=n) 。 14. 设有一个 10 阶对称矩阵 A 采用压缩存储方式（以行为主序存储：a11=1），则 a85 的地址为 33 (k=i(i-1)/2+j) (1=i,j=n) 。 15. 所谓稀疏矩阵指的是 非零元很少(tm*n)且分布没有规律 。16. 对矩阵压缩是为了 节省存储空间 。17. 上三角矩阵压缩的下标对应关系为： 上三角矩阵中，主对角线上第r(1rn) 行有n-r+1个元素，aij所在行的元素数是j-i+1。所以，元素在一维数组的下标k和二维数组下标关系:k=(i-1)*(2n-i+2)/2+(j-i+1)=(i-1)(2n-i)/2+j (ij)。18. 假设一个 15 阶的上三角矩阵 A按行优先顺序压缩存储在一维数组 B 中， 则非零元素 A9,9在 B中的存储位置k= 93 。 （注：矩阵元素下标从 1 开始）如果按行序为主序将下三角元素 Ai j (i,j)存储在一个一维数组 B 1.n(n+1)/2中，对任一个三角矩阵元素 A ,它在数组B 中的下标为 i(i-1)/2+j 。 8深度为k 的完全二叉树至少有1个结点，至多有2个结点。42一个无序序列可以通过构造一棵树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。50线索二元树的左线索指向其 ，右线索指向其 。53若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 。22. 已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd，则采用的是 深度优先 遍历方法。28. Prim（普里姆）算法适用于求 边稠密 的网的最小生成树；29克鲁斯卡尔算法的时间复杂度为 O(eloge）,它对 边稀疏 图较为适合。34. Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按 递增 次序依次产生，该算法弧上的权出现 负值 情况时，不能正确产生最短路径。12. 在哈希函数H（key）=key%p 中，p 值最好取 。49. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;1若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 比较 和记录的 移动 。6直接插入排序用监视哨的作用是 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。1. 文件可按其记录的类型不同而分成两类，即 操作系统文件 和 数据库 文件。7. 索引顺序文件既可以顺序存取，也可以 随机 存取。8. 建立索引文件的目的是 提高查找速度 。9. 索引顺序文件是最常用的文件组织之一，通常用 树 结构来组织索引。10. 倒排序文件的主要优点在于 检索记录快 。13. VSAM 系统是由索引集、顺序集、数据集构成的。31. 广义表A( ),(a,(b),c)，head(tail(head(tail(head(A)等于b32. 广义表运算式HEAD(TAIL(a,b,c),(x,y,z)的结果是 (x,y,z) 。33. 已知广义表A=（a，b），（c），（d，e），head（tail（tail（head（A）的结果是 (d,e) 。4、 应用题1线性表有两种存储结构：一是顺序表，二是链表。试问：如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O。选顺序存储结构。顺序表可以随机存取，时间复杂度为O。2线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。3若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？采用