当前位置:首页 >> 其它课程 >>

数据结构试题3


GDOU-B-11-302 广东海洋大学 2008——2009 学年第一学期
班 级 :

《数据结构》课程试题
课程号:

1620068

√ □考试 □
15 14 16 15

√ □3 卷

√ □闭卷 □
100

r />号 一 二 三 四 五 六 七 八 九 十 总分 阅卷教师
15 15

姓 名 :

各题分数 10


实得分数 一、填空题(10 ? 2’=20 分) 1、数据元素是( )的基本单位,在程序中通常作为一个( )进行处理。 2、数据结构是指相互间存在一定关系的( )的集合。 3、插入一个元素,线性表的长度( )1。 4、栈的操作特点是( ) 。 5、已知一棵二叉树的中序序列和后序序列分别为: DBGEACHF 和 DGEBHFCA,则 该二叉树的前序序列是( ) 。 6、对于含有 n 个顶点和 e 条边的无向连通图,利用普里姆算法产生的最小生成 树,其时间复杂度为( ) 、利用克鲁斯卡尔算法产生的最小生成树,其时间复杂 度为( ) 。 7、对于包含50个关键码的3阶 B-树,其最小高度为( ) ,最大高度为( ) 。 8、在插入和选择排序中,若初始数据基本正序,则选择( ) ,若初始数据基本 反序,则最好选择( ) 。 9、.在有 n 个结点的无向图中,其边数最多为( ) 。 10、在串 S="structure"中,以 t 为首字符的子串有( )个。 二、选择题(10 ? 2’=20 分) 1、算法分析的两个主要方面是( ) 。 A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 2、.顺序表是线性表的 ( ) A.链式存储结构 B.顺序存储结构 C. 索引存储结构 D. 散列存储结构 3、在线性表的下列运算中,不改变数据元素之间结构关系的运算是( ) 。 A.插入 B.删除 C.排序 D.定位 4、在一个单链表 HL 中,若要在指针 q 所指结点的后面插入一个由指针 p 所指 向的结点,则执行( ) 。 A. q->next=p->next; p->next=q; B. p->next=q->next; q=p; C. q->next=p->next; p->next=q; D. p->next=q->next; q->next=p; 5、设循环队列中数组的下标范围是 1~n,其头尾指针分别为 f 和 r,则其元素

学 号 :



试 题 共 页 加 白 纸 张

线

个数为( ) A. r-f B. r-f+1 C. (r-f) mod n+1 D. (r-f+n) mod n 6、以下说法正确的是( ) A.数组中每个数据元素的数据类型相同 B.数组是一组分散的内存单元 C.数组是一种复杂的数据结构, 数组元素之间的关系既不是线性的也不是树形的 D.使用三元组表表示稀疏矩阵的元素,有时并不能节省存储空间 7、常对数组进行的两种基本操作是( ) A.建立与删除 B.索引与修改 C. 查找与修改 D. 查找与索引 8、对于一个具有 n 个顶点和 e 条边的有向图,进行拓扑排序时,总的计算时间 为( ) A O(en) B O(n+e) C O(nlog2e) D O(elog2n) 9、以下说法正确的是 ( ) A.连通图的生成树,是该连通图的一个极小连通子图。 B.无向图的邻接矩阵是对称的,有向图的邻接矩阵一定是不对称的。 C.任何一个有向图,其全部顶点可以排成一个拓扑序列。 D.有回路的图不能进行拓扑排序。 10、使用递归的归并排序算法时,为了保证排序过程的时间复杂度不超过 O(nlog2n),必须做到 ( ) 。 A. 每次序列的划分应该在线性时间内完成 B. 每次归并的两个子序列长度接近 C. 每次归并在线性时间内完成 D. 以上全是 三、判断题(10 ? 2’=20 分) 1、数据的存储结构是数据的逻辑结构的存储映像,不仅要存储数据元素的值, 还要存储元素之间的相互关系。 ) ( 2、非线性结构中,至少存在一个元素不止一个直接前驱或不止一个直接后继。 ( ) 3、散列表是一种链式存储结构。 ) ( 4、设串 S 的长度为 n,则 S 的子串个数为 n(n+1)/2。 ) ( 5、设有两个串 p 和 q,求 q 在 p 中第一次出现的位置的运算称为字符定位。 ) ( 6、稀疏矩阵是指有少量非零元素的矩阵。 ) ( 7、任何一个非空广义表的表尾可以是原子也可以是子表。 ) ( 8、图 G 由两个集合 V(G)和 E(G)所组成,其中顶点集 V(G)和边集 E(G)都可以为 空集。 ) ( 9、图的深度优先搜索的方法不适于有向图。 ) ( 10、一组纪录的关键字为(50,80,56,29,35,84) ,利用快速排序的方法进行第一趟 排序后的结果为 35,29,50,56,80,84。 ) ( 。 四、算法阅读题(4 ? 5’=20 分) 阅读下面程序,在指定处填空。 1、读取队列长度 template <class T >

int CirQueue<T>::Length() { int length =(_____(1)___________) %____(2)________; return ______(3)_______; } 2、初始化一棵二叉树,构造函数调用 template <class T> BiNode<T>* BiTree<T>::Creat( ) { BiNode<T>* root; T ch; cout<<"请输入创建一棵二叉树的结点数据"<<endl; cin>>ch; if (ch=="____(1)_______") root = NULL; else{ root = new BiNode<T>; //生成一个结点 root->data=______(2)________; root->lchild =_______(3)_________; //递归建立左子树 root->rchild = Creat( ); //递归建立右子树 } return root; } 阅读下面程序,指出其算法的功能。 3、template <class T> void BiTree::LeverOrder(BiNode<T> *root) { front=rear=0; //采用顺序队列,并假定不会发生上溢 if (root==NULL) return; Q[++rear]=root; while (front!=rear) { q=Q[++front]; cout<<q->data; if (q->lchild!=NULL) Q[++rear]=q->lchild; if (q->rchild!=NULL) Q[++rear]=q->rchild; } } 4、template <class T> LinkList:: LinkList(T a[ ], int n) { first=new Node<T>; //生成头结点 r=first; //尾指针初始化

for (i=0; i<n; i++) { s=new Node<T>; s->data=a[i]; //为每个数组元素建立一个结点 r->next=s; r=s; //插入到终端结点之后 } r->next=NULL; //单链表建立完毕,将终端结点的指针域置空 } 五、算法设计题(2 ? 5’=10 分) 1、两栈共享空间出栈算法 Pop。 2、已知(k1,k2,…,kn,kn+1)是一个关键字序列,试将(k1,k2,…,kn, kn+1)调整为堆。 六、综合题(10 分) 设有大小不等的n 个数据组(n个数据组中数据的总数为m),顺序存放在空间区 D 内,每个数据占一个存储单元, 数据组的首地址由数组S 给出, (如下图所示) , 试编写将新数据x 插入到第i个数据组的末尾且属于第i 个数据组的算法,插入 后,空间区D 和数组S 的相互关系仍保持正确。

[提示]本题是在向量D内插入元素问题。首先要查找插入位置,数据x插入到第i 个数据组的末尾,即是第i+1个数据组的开始,而第i(1≤i≤n)个数据组的首 地址由数组s(即数组元素s[i])给出。其次,数据x插入后,还要维护数组s, 以保持空间区D和数组s的正确的相互关系。


相关文章:
数据结构(第3版)习题答案
数据结构(第3版)习题答案_理学_高等教育_教育专区。可以看看高等学校精品资源共享课程 十二五普通高等教育国家级本科规划教材 绪论 第 1 章 1.1 什么是数据结构?...
数据结构试卷及参考答案_3
数据结构试卷及参考答案_3_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档数据结构试卷及参考答案_3_工学_高等教育_教育专区。...
数据结构习题3
数据结构习题3_教育学_高等教育_教育专区。第三章一、概念题 (一)单项选择题 1、若用单链表来表示排队,则应选择( )。 A、带尾指针的非循环链表 B、带尾指...
数据结构复习题 (3)
数据结构复习题 (3)_IT认证_资格考试/认证_教育专区。数据结构复习题带答案 数据结构试卷(四) 一、选择题(每题 1 分共 20 分) 1.设一维数组中有 n 个...
数据结构模拟试题及答案3
数据结构》模拟试题 3 一、 单项选择题 1.带头结点的单向链表为空的判断条件是( ) (设头指针为 head) 。 A.head = =NULL B.head!=NULL C.head->...
数据结构课后习题3
数据结构课后习题3_理学_高等教育_教育专区。3.1 有 5 个元素,其进栈次序为:A、B、C、D、E,在各种可能的出栈次序中,以元素 C、 D 最先出栈(即 C 第一...
数据结构试题及答案
数据结构试题及答案_其它课程_高中教育_教育专区。数据结构试卷(一)... 1 数据...3. 假定一棵树的广义表表示为 A(C,D(E,F,G) ,H(I,J) ) ,则树中所...
数据结构试题3
数据结构试题3_理学_高等教育_教育专区。姓名 ___ 德州学院期末考试试卷( 至 学年第 学期)考试时间: 120 分钟 8.要连通具有 n 个顶点的有向图,至少需要( )...
数据结构试卷-3
数据结构试卷-3_从业资格考试_资格考试/认证_教育专区。三、简答计算题(52 分) 1.假设一棵二叉树的先序遍历序列为 ABCDEFGH,中序遍历序列为 CBDAEGHF, 请画...
数据结构试题 试卷三 含答案
、判断题(1 0 分) 1.二维数组是数组元素为一维数组的线性表,因此它是线性结构。( ) 2.每种数据结构都应具备三种基本运算:插入、删除和搜索。( ) 3.用...
更多相关标签:
数据结构面试题 | 数据结构试题 | 数据结构常见面试题 | java数据结构面试题 | 数据结构面试题及答案 | 数据结构试题及答案 | 数据结构自考试题 | 数据结构算法面试题 |