数据结构与算法

1、模拟题一、 单选题1. 数据结构在计算机内存中的表示是指（）oA.数据的逻辑结构B.数据结构C.数据的存储结构D.数据元素2. 数据的（）包括集合、线性结构、树形结构和图状结构四种基本类型。A.逻辑结构和存储结构B.存储结构C.逻辑结构D.物理结构3. 通常所说的时间复杂度是指（）。A.语句的频度和B.算法的时间消耗C.最坏时间复杂度D.渐近时间复杂度4. 线性表的顺序存储结构是通过（）的方式表示元素之间的关系。A.后继元素地址B.元素的存储顺序C.左、右孩子地址 D.后继元素的数组下标5. 在顺序栈S中插入元素e时，执行（）。A. S.top; *S.top = e;B. *S.top =

2、e; S.top+;C. *S.top = e; S.top-;D. S.top+; *S.top = e;6. 一个队列的入列序列是1, 2, 3, 4,则队列的输出序列是（）。A.4, 3, 2, 1B. 1, 4, 3, 2C. 1, 2, 3, 4D. 3, 2, 4, 17. 对于稀疏矩阵的压缩存储只需存储（）。A.所有元素B.对角线上的元素C.零元素D.非零元素&对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左 右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）。A.从根结点开始的层次遍历B.先序遍历C.中序遍历D.后序遍历9. 按二叉树的定义，具有

3、3个结点的二义树一共有（）种。A. 2B.3C.4 D. 510. 对于具有n个顶点和e条边的有向图，釆用邻接表表示，则表头向量的大小为（）。A. n B. n+1 C. n-1 D. n+e 11连通图的生成树是（）oA.极小连通子图B.顶点间可以无路径C.连通子图 D.边数为顶点数12.快速排序方法在()情况下最不利于发挥其长处。A.被排序数据已基本有序B.被排序的数据量太大C.被排序数据数U为奇数 D.被排序数据中含有多个相同值二填空题1. 中任何两个结点之间没有逻辑关系。2. 在线性表中，一个数据元素可曲若干数据项组成，常将此种数据元素称为o3. 在一个单链表中，若删除P所指结点的后继

4、结点，则执行O4. 栈的表尾称为o5. 入队操作要修改o6. 广义表是数据元素的有限序列，其元素可以是单个元素，也可以是o7. 深度为5的满二叉树的结点数为o&具有3个结点的树有种。9. Prim算法适用于边数较的图。10. 遍历是指按某种搜索路径访问二义树的每个结点，而且每个结点仅被访问o11. 对二叉排序树进行遍历，可以得到该二叉树所有结点构成的有序序列。12. 具有20个记录的序列，釆用起泡排序最多的比较次数为o三问答题1. 请用C语言给出顺序表的类型定义。2. 数据结构形式定义为(DS),其中 D=af bf c, d, e , S=Rf R=(a,b), (bi CX(c, M),

5、(c, e), (d, e) ,画出其逻辑结构图。3. 举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其效率不同。4.5.若某非空二叉树的先序序列和后序序列正好相同，试说明二叉树的形态及原因。6.以关键字序列12, 2, 16, 9, 10. 8, 20为例，写岀执行快速排序算法的各趟排序 结束时，关键字序列的状态。四算法题1. 下面算法的功能是：在无头结点的线性单链表中插入元素结点，即在第i个位置之前 插入新的数据元素e o请在空缺处填入相应的语句。StatUS LiStInSert-L(LinkLiSt &L, int i, EIenlTyPe e)L是该链表白6头指针if(

6、i=l)S=(LinkLiSt)nalloc(sizeof(LNode); s-data=e;(1) ;(2) ；else p=LJ=l;WhiIe (p&jnext; +j； if(!pllji-l)return ERROR; S=(LinkLiSt)maoc(sizeof(LNode) s-data=e;(3) :(4) ；)return OK;)2. 试写出下面操作算法的功能。VOid A(LinkLiSt &La, SqLiSt Lb) La=(LinkLiSt)malloc(sizeof (LNode); La-next=NULL;P=La;for (i=0; idata=Lb.el

7、emi;p-next=q;p=q;) q-next=NULL;模拟题1答案一单选题LC 4. B 6. C7. D 10. A 12. A二填空题1.集合2 记录5 队尾指针6. 广义表7. 316 29.多或者稠密12. 190三问答题1.typedef StrUCtElemTyPe *elem;int length;int listsize; SqList;2.3. 略4.5.略6.8, 2, 10, 9 1216, 202 8 10, 9 12, 16, 202, 8, 9, 10, 12, 16, 20四算法题1.(1) s-next=L; L=s;(3) s-next=p-next;

8、(4) p-next=s;2. 算法的功能是：建立一个带有头结点的单链表，链表中存储顺序表中的已有元素数据结构与算法模拟题一. 单选题1. 数据结构可形式地定义为(D.S),其中S是D上()的有限集。A操作B.存储映像C.关系D.数据元素2. 数据的最小单位是（）=A.数据结构B.数据元素C.数据项D.文件3. 下列数据结构中（）是线性数据结构。A.二叉树B.无向图 C.赫夫曼树D.队列4. 采用链式存储结构存储线性衣的优点是（）。A.便于随机存取B.花费的存储空间比顾序存储少C.便于插入和删除操作D.数据元素的物理顺序与逻辑顺序相同5. （）不是队列的基本运算。A.判断一个队列是否为空B.从

9、队头删除一个元素C.在队列第i个元素之后插入个元素 D.读取队头元素的值6. 个队列的入列序列是123.4,则队列的输出序列是（A.4,321B.324JCl 43,2D23,4)7.广义农(a),(b)的表尾是(A.()B.b)oC. (b)D. (b)8.若无向图中有n个结点，e条边，则它的邻接衣需要（A. nB. 2nC. 2eD. e）个农结点。9.在哈希函数H（key） = key%m中，般来说，m应取（A.奇数 B.偶数 C.充分大的数 D.素数)10. 赫夫曼树的带权路径长度是（）。A.所有叶结点带权路径长度之和B.所有结点权值之和C.带权结点的值D.除根以外所有结点权值之和11

10、. 设-个有序农为L 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100,当采用折半查找值为95的结点时，（）次比较后查找结束。A.3B.4C.5D.612.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）oA.直接插入排序B.快速排序C.冒泡排序D.简单选择排序二、填空题1.在线性衣中，个数据元素可由若干数据项组成，在这种情况下，常将数据元素称为2. 在图形结构中，每个结点的前驱结点和后继结点可以有。3. 从逻辑结构来看，线性结构的特点是。4栈又称为的线性农。5. 设有个顺序栈S,元素a.b.c,d.e,f依次入栈，如果6个元素的出栈

11、顺序为b,c.a,d.f.e,则顺序栈的容量 至少为o6. 在队列中，可进行删除操作的端称为o7. 对于稀疏矩阵的压缩存储只需存储0&邻接农是图的存储结构。9. 在棵度为3的树中，度为3的结点个数为2,度为2的结点个数为I,则度为O的结点为个。10. 有100个结点的树有条边。H. 对二叉扌IE序树进行遍历，可以得到该二叉树所有结点构成的有用序列。12.起泡排序、快速排序和插入排用中，不稳定的是O三、解答题I. 请用C语言给出单链衣（线性农的链式存储结构）的类型定义。2.设有多项式A（X） = 1 + 3x + 2x4,试用线性链衣农示。3. 设有-个二维数组A1020,采用以行序为主序的存储

12、结构，每个元素占两个空间，第个元素的存 放位置为100（十进制），求元素A68的存放位置。4. 将如下树转换成二叉树C5. 哈希查找算法与其他查找方法对比有何特点？何谓冲突？请写出两种解决冲突方法的名称。6.设哈希农农长为11,哈希函数(用除留余数法H(key) = key mod 11,解决冲突的方法为开放定址法 Hi(key)=(H(key)+di)modll,对下列关键字序列19, 13, 33, 02, 6 24, 7,给出计算过程并构造哈希 表。四、算法题1 在长度人于1的带头结点的单链衣中，P为指向待处理结点的指针，pre为指向最小值结点的前驱结点 的指针。下面算法的功能是：删除最

13、小值结点。请在空缺处填入相应的语句。VOid DeIete(LinkLiSt &L)P = L-next;Pre = L;q=p:While( (1)if (p-next-data data)(2) :(3) :(4) :pre-next = q-next;free(q);2阅读如下算法，给出该算法的功能。VOid UnknOwn(LinkLiSt &L, int n)L= (LinkLiSt) malloczeof(LNode);L-next=NULL:s=L;for (i = n: iO-i)P =(LinkLiSt)malloc(sizeof(LNode); p-data=i;s-nex

14、t = p:s = p;s-next = NULL;模拟题2参考答案一、单选题1. C4. C5. C7. C9. D12. A二、填空题1. 记录2. 多个4. 后进先岀5.27.非零元素&链式11. 中序；12. 快速排序三、解答题1. typedef StnlCt LNodefEleInTyPe data;StrUCt LNOde *next:LNode, *LinkList;3.LOC(ij)=LC(0,0)+(b2*i+j)L100+(20*6+8)*2=3564.5. 哈希查找算法不经过任何比较。冲突:对不同的关键字得到相同的哈希地址，这种现象称为冲突。开放定址法和链地址法6.Ol

15、 23456789103313022416719四.I算法题1 (1)p-next != NULLPre = p;q = p-next;P = p-next;2.算法的功能是：正位序（即从衣头到衣尾）建立个带头结点的线性单链农。数据结构与算法模拟题3一、单选题1. 计算机算法具有输入、输出和（）这五个特征。A. 可行性、确定性和有穷性 B.可行性、可移植性和可扩充性C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性2. 线性农中的顺序存储结构是通过何种方式农示元素之间的关系（）。A. 后继元素地址B.元素的存储顺序C.左、右孩子地址D.后继元素的数组下标3. 最适合描述算法的语言是（）。A

16、.自然语言B.计算机程序语言C介于自然语言和程序设计语言之间的伪语言D.数学公式4. 釆用链式存储结构存储线性农的优点是（）=A.便于插入和删除操作B.便于随机存取C.花费的存储空间比顺序存储少D.数据元素的物理顺序与逻辑顺序相同5在哈希函数H（key） = key%m中，般来说，m应取（）。A.充分大的数B.素数 C.奇数 D.偶数6. 在顺序栈中删除元素时，是（）。A. 先删除元素，再移动栈顶指针B. 不分先后，同时进行C. 先移动栈顶指针，再删除元素D. 谁先谁后都可以7. 广义衣（a）,（b）的衣尾是（）。A. （b）B.bC.（b）D.（）&设有-个二维数组A1020,采用以行序为主

17、序的存储结构，每个元素占两个空间，第个元素的存 放位置为100（十进制），则元素A66的存放位置为（）。A.320（十进制）B. 352 （十进制）C300（十进制）D. 232 （十进制）9常对数组进行的两种基本操作是（）。A.查找和插入B.插入和修改C.查找和修改D.建立和删除10.已知某二叉树的先序遍历为A, B, D, C, E,则它可能的中序遍历序列为（A.B, C, A, D, EB.C, B, A, D, EC.B. D, A, E. CD.B E, A, C, D11下Ifri关于图的存储的叙述中，（）是正确的=A. 用邻接衣存储图，占用的存储空间数与图中结点个数有关，与边数无

18、关B. 用邻接衣存储图，占用的存储空间数与图中边数有关，与结点个数无关C. 用邻接矩阵法存储图，占用的存储空间数与图中结点个数有关，与边数无关 D用邻接矩阵法存储图，占用的存储空间数与图中边数有关，与结点个数无关12. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.冒泡排序B.快速排序C.直接插入扌旧了：D.简单选择扌旧予二、填空题1. 计算机算法具有输入、输出、可行性、有穷性和这五个特征。2. 数据的基本单位是。3. 在图形结构中，每个结点的前驱结点和后继结点可以有o4. 在单链农中，头结点的作用是。5队列具有的特点。6. 二维数组的两种顾序存储结构分别为以行序为主

19、疗:的方式和以为主用的方式。7. 对于稀疏矩阵的压缩存储只需存储O&广义农（a）的衣尾是o9.对于个具有7个结点的二叉树，当它为-棵二叉树时具有最小高度。10设无向图G的顶点数为n,则G最少有条边。11. 对二叉扌IE序树进行遍历，可以得到该二叉树所有结点构成的有用序列。12. 具有20个记录的序列，采用起泡排序最少的比较次数为O三、解答题1. 请用C语言给出顺序栈（栈的顺序存储结构）的类型定义。2. 有字符串序列为“3*-yay试利用栈将字符串次序改为“3yay/”，请写出操作步骤。（可用X代农扫 描该字符串过程中顺序取个字符进栈的操作，用S代衣从栈中取岀-个字符加入到新字符串尾的操作。 例

20、如：ABC变为BCA,则操作步骤为XXSXSS）O3. 按行序为主序列出三维数组A232的所有元素在内存中的存储次序。4. 用3, 6, 7, 8. 30作为叶/结点的值生成棵赫夫曼树，并计算该树的带权路径长度。5在棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为O的结点个数是多少。6.以关键字序列12, 2, 16, 9, 10, 8, 20为例，分别写出执行以下排序算法的各趟排序结束时,关键 字序列的状态。(1)直接插入排序(2)快速排胖四、算法题1.下面算法的功能是：建立个带有头结点的单链衣，链衣中存储顺疗:农中的已有元素。请在空缺处填 入相应的语句。VOid A(Li

21、nkLiSt &La, SqLiSt Lb) La=(LinkLiSt)malloc(sizeof (LNode);La-next=NULL;(1) :for (i=0; idata=Lb.elemi;(2) :(3) :(4) :2阅读如下算法，给出该算法的功能。VOid UnknOW(SIaCk &S)Q是局部变量-队列InitQueue(Q);While(!StackEmpty(S)4/4 i=Pop(S); EnQUeUe(QJ);While(!QueueEmpty(Q) i=DeQueue(Q); Push(Sj); 一、判断题 、ACDC CDCA DAAA-ZZL %1、记录2多

22、个（任恿）3、略4、后进先出/先进后出5、26、略7、非零元&链式9、6IOS略n、中序12、快速排序四、略2A叱勿-Il-Hi( I 十胡3 |1 I 4TT丽3.(6*208) *2+100=3564、略五、1. 下列程序判断字符串S是否对称，对称则返回1,否则返回0；如ffabba”）返回1,（1） Chars （2） j+（3） i=j2. 阅读如下算法，给出该算法的功能。程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底， 栈底的元素放到栈顶。此栈中元素个数限制在64个以内。一、判断题1. 记录是数据处理的最小单位。（）2. 两维数组是一种非线性结构。（）3.

23、 在某棵二义树的一种序列中，如果发现其中每一结点的左孩子均是其前趋，则可 判断定这种序列为中序序列（）。4. 前序遍历和后序遍历结果相同的二义树为只有根结点的二义树（）。5. 在任一有向图中，所有顶点的入度之和一定等于所有顶点的出度之和（）。二、单选题1. 若要求能快速地实现在链表的末尾插入结点和删除第一个结点的运算，则选择（） 最合适。A）单链表B）带尾指针的单循环链表C）双链表D）双循环链表2. 利用n个值生成的哈夫曼树中共有（）个结点。A. n B. nl C. 2n D. 2nl3. 在各种排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元 素进行比较，将其放入已排

24、序序列的正确位置上的方法，称为（）。A）希尔排序B）冒泡排序C）插入排序D）选择排序4. 一个栈的入栈序列是a,b,c,d,则下列序列中不可能的输出序列是（）。A)acbd B)dcba C)acdb D)dbac5. （）不是队列的基本运算。A. 判断一个队列是否为空B.从队头删除一个元素C.在队列第i个元素之后插入个元素D.读取队头元素的值6. 个队列的入列序列是123.4 ,贝IJ队列的输出疗:列是（A43,2,1B.324JC.4,3,2D 1,2,3,47.广义衣(a).(b)的衣尾是()。D(b)A.( )B.bC. (b)8. 若无向图中有n个结点，e条边，则它的邻接衣需要（）个

25、农结点。A. nB. 2nC. 2eD. e9 常对数组进行的两种基本操作是（）。A.查找和插入B.插入和修改C.査找和修改D.建立和删除10.已知某二叉树的先序遍历为A, B, D, C, E,则它可能的中序遍历序列为（）。A.B, C, Af Dt EB.C, Bf A, D, EC.B, D, Af E, CD.B, E, A, C, D11下而关于图的存储的叙述中，（）是正确的=A. 用邻接衣存储图，占用的存储空间数与图中结点个数有关，与边数无关B. 用邻接农存储图，占用的存储空间数与图中边数有关，与结点个数无关C. 用邻接矩阵法存储图，占用的存储空间数与图中结点个数有关，与边数无关 D用邻接矩阵法存储图，占用的存储空间数与图中边数有关，与结点个数无关 12.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）oA.冒泡排席B.快速排序C.直接插入排序D.简单选择排序三. 填空题1. 数据的逻辑结构可分为和两大类。2. 数据的存储结构被分为，, 和4种。3. 在