数据结构考试题(20页).doc

-一、 单项选择1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 C 、数据信息在计算机中的 A 以及一组相关的运算等的课程。 A操作对象计算方法逻辑结构数据映象 A存储结构 关系 运算 算法2. 以下数据结构中, D 是线性结构。 A广义表二叉树稀疏矩阵串3. 从逻辑上可以把数据结构分为 C 两大类。 A动态结构和静态结构 顺序结构和链式结构 线性结构和非线性结构 初等结构和构造型结构 4. 以下数据结构中, D 是线性结构。 A广义表二叉树稀疏矩阵串5. 以下数据结构中, D 是非线性结构。 A栈 二叉树队列 字符串6. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是 B 的有限集合，R是D上的 D 有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系7. 线性表的顺序存储结构是一种 A 的存储结构, 线性表的链式存储结构是一种的 B 存储结构。A随机存取 顺序存取 索引存取 散列存取8. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_B _。A. 正确 B. 不正确9. 下面那一条是顺序存储结构的优点? (A)A . 存储密度大 B. 插入运算方便 C. 删除运算方便 D. 可以方便的用于各种逻辑结构的存储表示10. 线性表采用链式存储结构时, 要求内存中可用的存储单元的地址 .A . 必须是连续的 B. 部分地址必须是连续的 C. 一定不连续D. 连续和不连续都可以11. 表长为n的顺序存储的线性表, 当在任何位置上插入和删除一个元素的概率相等时, 插入一个元素所需要移动元素的平均次数为 E , 删除一个元素所需要移动元素的平均次数为 A A. (n-1)/2 B.n C. n+1 D. n-1 E. n/2 F. (n+1)/2 G. (n-2)/212. 带头结点的单链表head为空的判定条件是_B_。A. head= =NULL B. head->next= =NULLC. head->next= =head D. head!=NULL13. 在一个单链表中, 若删除p所指向结点的后继结点, 则执行_A_。A. p->next= p->next->next B. p=p->next; p->next= p->next->nextC. p= p->next->next D. p= p->next14. 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为_C_。 A. i B. n=i C. n-i+1 D. 不确定15. 设栈的输入次序为: 1 , 2, 3, 4, 5, 则 不可能是其出栈序列. A. 54321 B. 45321 C. 43512 D. 1234516. 一个递归算法必须包括 B A. 递归部分 B. 终止条件和递归部分C. 迭代部分 D. 终止条件和迭代部分17. 用链接方式存储的队列, 在进行删除操作时 D A 仅修改头指针 B. 仅修改尾指针C. 头尾指针都要修改 D. 头尾指针可能都要修改18. 数组Am存放循环队列的元素, 其头尾指针分别是front和rear, 则当前队列的元素个数是_A_。A. (rear-front+m)%m B. (front-rear+m)%m C. front-rear+1 D. rear-front+119. 栈和队列的共同特点_C_。A. 都是先进先出 B. 都是先进后出 C. 允许在端点插入和删除元素 D. 没有共同点20. 一个栈的入栈序列a，b，c，d，e，则栈的输出序列是_A_。 A. edcba B. decba C. dceab D. abcde 21. 栈的特点是_B_，队列的特点是_A_。A. 先进先出 B. 先进后出22. 从一个栈顶指针HS的链表中删除一个结点, 用x保存被删除的结点值,执行的语句为_C_。A. x=HS; HS=HS->next B. HS=HS->next; x=HS->dataC. x=HS->data; HS=HS->next D. HS->next=HS; x=HS->data23. 在链队列Q中, 插入s所指向的结点执行的语句为_C_。A. Q.front->next=s; B. Q.rear->next=s; Q.rear=sC. s->next=Q.rear;Q.rear=s D. s->next=Q.front;Q.front=s24. 空串与空格串是相同的，这种说法_B_。A. 正确 B. 不正确25. 下面关于串的叙述, 哪一个是不正确的_B_。A. 串是字符的有限序列 B. 空串是由空格构成的串C. 匹配模式是串的一种重要运算 D. 串可以采用链式存储结构26. 设有两个串p和q，求q在p中首次出现的位置的运算称作_B_。A. 连接 B. 模式匹配C. 求子串 D. 求串长27. 若串s='software', 其子串的数目为 B A. 8 B. 37 C. 36 D. 928. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为_C_。A. SA+141 B. SA+144 C. SA+222 D. SA+22529. 对稀疏矩阵进行压缩存储的目的是_C_.A. 便于进行矩阵运算 B. 便于输入输出C 节省存储空间 D. 降低运算的时间复杂度30. 在以下叙述中正确的是 B A. 线性表的线性存储结构优于链表存储结构B. 二维数组可以看成是其数据元素为线性表的线性表C. 栈的操作方式是先进先出D. 队列的操作方式是先进后出31. 广义表(a),a)的表头为 C , 表尾为 C .A. () B. a C. (a) D. (a)32. 已知广义表L=(x,y,z),a,(u,t,w), 从L中取出原子项t的运算为_D_。 A. Head(Tail(Tail(L) B. Tail(Head(Head(Tail(L)C. Head(Tail(Head(Tail(L) D. Head(Tail(Head(Tail(Tail(L)33. 树最适合用来表示 B A. 有序的数据元素 B. 数据之间具有分支层次关系的数据C. 无序的数据元素 D. 无太多关系的数据元素34. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为_B_。 A. uwvts B. vwuts C. wuvts D. wutsv35. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_D_。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca36. 在一非空二叉树的中序遍历序列中，根结点的右边_A_。A. 只有右子树上的所有结点 B. 只有右子树上的部分结点C. 只有左子树上的部分结点 D. 只有左子树上的所有结点37. 设m和n是一棵二叉树上的两个结点, 在中序遍历, n在m前的条件是 C A. n在m的右方 B. n是m的祖先C. n在m的左方 D. n是m的子孙38. 深度为5的二叉树至多有_C_个结点。A. 16 B. 32 C. 31 D. 1039. 由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树, 该树的带权路径长度为 D A. 23 B. 37 C. 46 D. 4340. 利用二叉链表存储树, 则根结点的右指针是 C A. 指向最左孩子 B. 指向最右孩子 C. 空 D. 非空41. 下列存储方式中, 哪一个不是树的存储形式? D A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法42. 在一个无向图中，所有顶点的度数之和等于所有边数的_C_倍。A. 1/2 B. 1 C. 2 D. 4 43. 具有n个顶点和多于n-1条边的无向图 B .A. 有可能是树 B. 一定不是树 C. 一定是树 D. 以上答案都不对44. 具有6个顶点的无向图至少应有_A_条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 845. 无向图G=(V,E), 其中: V=a,b,c,d,e,f, E=(a,b),(a,e),(a,c), (b,e),(c,f),(f,d),(e,d), 则对该图进行深度优先遍历, 得到的序列为: D A. abecdf B. acfebd C. aebcfd D. aedfcb46. 下述几种排序方法中，要求内存量最大的是_D_。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序47. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_C_。A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序48. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A_。A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序49. 下列排序算法中, 哪一个是稳定的排序算法? B A. 直接选择排序 B. 二分法插入排序 C. 希尔排序 D. 快速排序50. 将两个各有n个元素的有序表归并成一个有序表, 其最少的比较次数 A A. n B. 2n-1 C. 2n D. n-1二、 填空题1. 算法的五个重要特性是 有穷性,确定性,可行性,输入和输出.2. 数据的树型结构和图(网)状结构合称 非线性结构 .3. 抽象数据类型的定义仅取决于它的一组 逻辑特性 , 而与 数据在计算机中的表示和实现 无关.4. 评价算法质量的指标是 正确性,易读性,健壮性,高效性.5. 数据结构中评价算法的两个重要指标是: 时间复杂度和空间复杂度.6. 分析下面算法（程序段），的时间复杂度是_ O (mn) _。s=0;for (i=0;i<n;i+) for (j=0;j<m;j+) s+=Bij;7. 当线性表元素的总数基本稳定, 且很少进行删除和插入操作时, 但是要求以最快的速度存取线性表中的元素, 应该采取 顺序 存储结构.8. 顺序表中逻辑上相邻的元素的物理位置 必定 相邻, 而单链表中逻辑上相邻的元素的物理位置 不一定 相邻.9. 在各个结点查找概率相等的情况下, 从n个结点的单链表中查找一个结点, 平均要访问 n/2 个结点.10. 在单链表中设置头指针的作用是: 简化操作, 减少边界条件的判断.11. 在单链表中, 除首元结点外, 任一结点的存储位置由 其直接前驱的指针域 指示.12. 对于一个具有n个结点的单链表, 在已知p所指向结点后插入一个新结点的时间复杂度是 O(1) , 在值域为给定值的结点后插入一个新结点的时间复杂度为O(n). 13. 在双链表中，每个结点有两个指针域，一个指向_前驱结点_，另一个指向_后继结点_ _。14. 根据线性表的链式存储结构中每一结点包含的指针个数, 将线性表分成 单链表 和 多重链表.15. 在非空双向链表中, 在结点q的前面插入结点p的过程如下, 请补充 p->prior=q->prior;q->prior->next=p;p->next=q;q->prior=p;16. 一般情况下, 将递归算法转换成等价的非递归算法应该设置 栈 .17. 在解决计算机主机与打印机速度不匹配问题时, 通常设置一个打印数据缓冲区, 该缓冲区通常是一个 队列 数据结构.18. 循环队列的引入, 目的是为了克服 假溢出 现象.19. 在栈顶指针为HS的链栈中, 判断栈空的条件是 HS=NULL .20. 在具有n个单元的循环队列中, 如果不专门设置队满标志, 则队满时共 n-1 有个元素.21. 实现字符串拷贝的函数如下, 请补足Void strcpy(char *s, char *t) while( (*s+=*t+)!='0' );22. 空格串是_由一个或多个空格字符组成的串 _，其长度等于_其包含的空格个数 。23. 空串是 不包含任何字符的串 , 其长度为 0 .24. 设s='I AM A STUDENT', 其长度为: 14 .25. 组成串的元素只能是: 字符 .26. 设s1='Good', s2=' ', s3='bye!', 则s1,s2和s3连接的结果是 Good bye!27. 若广义表中每个元素都是原子时, 广义表便成为 线性表 .28. 广义表的表尾是指除第一个元素外, 剩余元素组成的表 .29. 广义表A=(a,b,c,d)的表头为 (a,b,c,d) ,表尾为 () .30. 数组的存储结构采用 顺序 存储方式.31. 设二维数组a0.5, 0.6, 其每个字节占5个字节, 第一个元素的存储地址为1000, 若按列存储, 则元素a5,5存储地址为 1175 .32. 高度为k的完全二叉树至少有 个叶子结点.33. 若一棵二叉树有50个叶子结点, 则该二叉树的总结点数至少是 99.34. 有n个叶子结点的哈夫曼树的结点总数为 2n-1 .35. 根据二叉树的定义, 具有三个结点的二叉树有 4 种.36. 某棵二叉树的中序遍历序列为abcdefg, 后序遍历序列为 bdcafge, 则该二叉树的前序遍历序列 eacbdgf , 该二叉树对应的森林包含 2 棵二叉树.37. 若二叉树采用二叉链表存储结构, 要交换其所有分支结点的左,右子树的位置, 利用 中序 遍历方法最为合适.38. 线索二叉树的左线索指向其 前驱 , 右线索指向其 后继 .39. 树所对应的二叉树其根结点的 右 子树一定为空.40. 利用树的孩子兄弟表示法存储, 可以将一棵树转化成 二叉树.41. 设无向图的顶点个数为n, 则该图最多有 n(n-1)/2 条边.42. n个顶点的连通图至少有 n-1 条边.43. 已知一个图用领接矩阵表示, 计算第i个结点的入度的方法是 求第i列非零元素的和 .44. G是一个非连通的无向图, 共有28条边, 则该图至少有 9 个顶点.45. 一个图的 邻接矩阵 表示法是唯一的，而 邻接表 表示法是不唯一的。46. 从邻接矩阵可以看出, 该图共有 3 个顶点, 如果是无向图, 则共有 2 条边.47. n个顶点的连通图用邻接矩阵表示时, 则该矩阵至少有 2(n-1) 个顶点.48. 设图中有n个顶点, e条边, 如果用邻接表表示图, 进行深度优先搜索遍历的时间复杂度为 O(n+e) , 如果用邻接矩阵表示图, 时间复杂度为 49. 从平均时间性能而言, 快速排序 排序最佳.50. 堆排序是一种 选择 排序, 堆实质上是 一棵完全二叉树 结点的层次序列. 对于含有n个元素的排序, 堆排序的时间复杂度为 . 所需附加的存储结点是 O(1) .三、 用图表回答下列问题1. 设某通信系统使用A，B ，C，D，E，F，G，H个字符，出现的频率w=，试构造对应的哈夫曼树（请按左子树根结点的权小于右子树树根结点的权的次序构造）?答案如图:D8F23H111942A5B29C7E14G381529581002. 根据下面的邻接链表，画出相应的图，写出每个顶点的度, 并用邻接矩阵表示.v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3答案如图所示:v1v2v3v4v5V6V1: 3V2: 2V3: 3V4: 2V5: 4V6: 23. 画出下列树对应的二叉树，并写出其先根遍历序列：BDFCAEG先根遍历序列： A B D E G F C 答案如图所示:BEGDFCA 4. 画出和下列二叉树对应的森林：AAAABBBCCC答:AAAABBBCCC四、 阅读下列算法，按要求做答.1. 下面是删除单链表L中最大元素所在结点的类C语言算法, 请补足缺失部分使其完整.void DelMax(LinkList L)r=L; p=L->next; if(p) m=p->data; (1) ; p=p->next; while(p) if( (2) ) (3) ; m=p->data; (4) ; p=p->next;q=r->next; (5) ; free(q); 答案: (1) L->next=NULL ; (2)p!=NULL; (3)q!=NULL ; (4) p->next=r->next (5) r->next=p.2. 阅读下列算法，说明该算法的作用。Status algorithm1(LinkQueue &Q)SqStackStack;QElemTypeElement;InitStack(Stack);while(!QueueEmpty(Q)DeQueue(Q,Element);Push(Stack,Element);while(!StackEmpty(Stack)Pop(Stack,Element);EnQueue(Q,Element);答: 利用栈实现队列的逆置.3. 阅读下列算法，说明该算法的作用。Status algorithm2(Stack S, int e)StackT;intd;InitStack(T);while(!StackEmpty(S)Pop(S,d);if(d!=e) Push(T,d); while(!StackEmpty(T)Pop(T,d);Push(S,d);答: 利用辅助栈T, 将栈S中的元素e删除.4. 将下面程序改写成递归过程.void algorithm3(int n)inti=n; while(i>1)printf(i-);答: void algorithm4(int j)if(j>1)printf(j);algorithm4(j-1)5. 阅读下列算法，说明该算法的作用。BiTree algorithm5(ElemType Pre, ElemType In)int PreLen, InLen;int i, j;BiTree BT;ElemType *subPre, *subIn;PreLen = strlen(Pre);InLen = strlen(In);if (PreLen != InLen | PreLen = 0) return NULL;for (i=0; i<InLen && Ini!=Pre0; i+);if (i = InLen) return NULL;BT = (BiTNode *) malloc(sizeof(BiTNode);BT->data = Pre0;subPre = (ElemType *) malloc(i+1)*sizeof(ElemType);subIn = (ElemType *) malloc(i+1)*sizeof(ElemType);for (j=0; j<i; j+)subPrej = Prej+1;subInj = Inj;subPrej = '0' subInj = '0'BT->lchild = CreatBT(subPre, subIn);subPre = (ElemType *) malloc(PreLen-i)*sizeof(ElemType);subIn = (ElemType *) malloc(PreLen-i)*sizeof(ElemType);for (j=i+1; j<PreLen; j+)subPrej-i-1 = Prej;subInj-i-1 = Inj;subPrej-i-1 = '0' subInj-i-1 = '0'BT->rchild = CreatBT(subPre, subIn);return BT;答: 利用一棵二叉树的先序遍历和中序遍历还原该二叉树.五、 算法设计题1. 设顺序表L中的数据元素递增有序. 试写一个算法, 将e插入顺序表中, 要求插入后保持该表的有序性.void InsertElem(SqList &L, ElemType) j=L.length-1; while(L.elemj>e)L.elemj+1=L.elemj;j+ L.elemj+1=e; L.length+;2. 已知la是带头结点的单链表的头指针, 试编写一个逆序输出表中各个元素的递归算法.void TraverseLink(LinkList p) if(p->next) TraverseLink(p->next); printf(p->data);3. 写一算法，统计二叉树的结点的总个数。/利用中序遍历方法，或者先序、后序均可以void Leaf(BiTree T, int &m) if (T!=NULL) Leaf(T->lchild, m); /中根遍历左子树 m+; /计算结点 Leaf(T->rchild, m); /中根遍历右子树 4. 写一算法，求二叉树的高度。int height(BiTree T) if (T = NULL) return 0; else int hl=height(T->lchild); int hr=height(T->rchild); return 1 + (hl>hr?hl:hr); /1加上hl和hr的较大值 5. 写一算法，交换二叉树的左右子树。BiTNode Permute_child(BiTNode *T) BiTNode *temp; if(T) Permute_child(T->lchild); Permute_child(T->rchild); temp=T->lchild; T->lchild=BT->rchild; T->rchild=temp; 6. 已知二叉树采用二叉链表存储, 设计算法, 判定两棵二叉树是否相似.Statues like(BiTree S, BiTree T) if(T=NULL && S=NULL) return 1; else if (S && T) return (like(S->lchild , T->lchild) && like(S->rchild , T->rchild); else return 0;-第 20 页-