数据结构试题2new

《数据结构试题2new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、广东海洋大学2008--2009学年第一学期《数据结构》课程试题课程号：1620068□√考试□√2卷□√闭卷□□　　题号一二三四五六七八九十总分阅卷教师各题分数201510202015100实得分数一、填空题（102'=20分）1、数据是（）的载体。2、数据对象是具有（）的数据元素的集合。3、线性表的（）称为单链表。4、栈和队列在逻辑上都是（）结构。5、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（）个字符编码。6、快速排序在平均情况下的时间复杂度为（），在最坏情况下的时间复杂度为（）。7、已知

2、一算术表达式的中缀形式为A＋B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()。8、带头结点的双循环链表L为空表的条件是（）。9、对于一个有10000个结点的二叉树，树叶最多有（）个，最少有（）个。10、设目标串T="abccdcdccbaa",模式P="cdcc"，则第（）次匹配成功。二、选择题（102'=20分）1、在存储数据时，通常不仅要存储个数据元素的值，而且还要存储（）。　　A：数据的处理方法B：数据元素的类型C：数据元素之间的关系D：数据的存储方法2、静态链表中指针表示的是（）.A.内存地址B.数组下标C.下一元素地址D

3、.左、右孩子地址3、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（）As=rear;rear=rear->link;deletes;Brear=rear->link;deleterear;Crear=rear->link->link;deleterear;Ds=rear->link->link;rear->link->link=s->link;deletes;4、使用两个栈共享一片内存空间时，当()时，才产生上溢。A.两个栈的栈顶同时

4、到达这片内存空间的中心点B.其中一个栈的栈顶到达这片内存空间的中心点C.两个栈的栈顶在这片内存空间的某一位置相遇D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底5、以下说法错误的是()A.二叉树可以是空集B.二叉树的任一结点都有两棵子树C.二叉树与树具有相同的树形结构D.二叉树中任一结点的两棵子树有次序之分6、若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（　）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目7、在一个带权连通图G中，权值最小的边一定包含在G的()生成树中　　A.某个最小B.任何

5、最小C.广度优先D.深度优先8、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）A．选择排序B．希尔排序C．归并排序D．快速排序9、对5个不同的数据元素进行直接插入排序，最多需要进行()次比较。A.8B.10C.15D.2510、若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏

6、情况下的时间复杂度是（）A．O（n/3）B．O（n）C．O（n2）D．O（n3）三、判断题（102'=20分）1、在数据结构中，从逻辑上可以把数据结构分成动态结构和静态结构。（）2、链表的主要缺点是不能随机访问。（）3、对于一个栈，若输入序列为A,B,C,D，则可以得到出栈序列C,A,B,D。（）4、判定一个队列QU（最多元素为m0）为空的条件是QU->front==QU->rear。（）5、向一个栈顶指针为HS的链栈中插入一个s所指结点时，执行s->next=HS->next;HS->next->s。（）6、在广义表的存储结构中，单元素结点与

7、表元素结点有一个域对应不同，各自分别为值域和子表指针域。（）7、二维数组A中，每个元素的长度为3个字节，行下标i的范围为0-7，列下标j的范围为0-9，从首地址S开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为S+180。（）8、网络的最小生成树是唯一的。（）9、图遍历时，图的广度优先搜索中邻接点的寻找具有"先进先出"的特征。（）10、完成堆排序的全过程需要N个记录大小的辅助空间。（）四、算法阅读题（45'=20分）阅读下面程序，在指定处填空。1、在队尾插入一个元素templatevoidCirQueue

8、::EnQueue(Tx){if((rear+1)%QueueSize==____(1)________)throw"上溢";rear=____