电大数据结构考试题10年1.doc
18页
. . .数据结构 （本）期末综合练习2010 年 12 月期末综合练习一一、单项选择题1．数据的物理结构 （）A． 与数据的逻辑结构无关B． 仅仅包括数据元素的表示C． 只包括数据元素间关系的表示D． 包括数据元素的表示和关系的表示2．数据元素是数据的基本单位，它（）A ．只能有一个数据项组成B． 至少有二个数据项组成C． 可以是一个数据项也可以由若干个数据项组成D ．至少有一个数据项为指针类型3． 从 n 个数中选取最大元素，（）A． 基本操作是数据元素间的交换B． 算法的时间复杂度是 O(n 2 )C． 算法的时间复杂度是O(n)D． 需要进行 (n+1) 次数据元素间的比较4．线性表的顺序结构中 ，（）A． 逻辑上相邻的元素在物理位置上不一定相邻B． 数据元素是不能随机访问的C． 逻辑上相邻的元素在物理位置上也相邻D． 进行数据元素的插入、删除效率较高.下载可编辑 .. . . .5 ． 以下表中可以随机访问的是 （ ）A． 单向链表 B． 双向链表C． 单向循环链表 D． 顺序表6 ． 带头结点的单向链表为空的判断条件是 （ ）（设头指针为 head ）A． head = =NULL B． head->next= =NULLC．head->next= =head D． head!=NULL7 . 设顺序存储的线性表长度为 n ，对于删除操作 ，设删除位置是等概率的 ，则删除一个元素平均移动元素的次数为 （ ）。
A． (n+1)/2 B． n C． 2n D ．n-i8 ． 线性结构中数据元素的位置之间存在 （ ）的关系 A． 一对一 B． 一对多C． 多对多 D ．每一个元素都有一个直接前驱和一个直接后继9． 设 top 是一个链栈的栈顶指针 ，栈中每个结点由一个数据域 data 和指针域 next 组成，设用 x 接收栈顶元素 ，则出栈操作为 （ ）A． x=top->data;top=top->next; B． top=top->next;x=top->data;C． x=top-> next;top=top-> data; D ．top->next =top; x=top->data;10． 设顺序存储的线性表长度为 n，要删除第 i 个元素 ，按课本的算法 ，当 i= （ ）时，移动元素的次数为 3A． 3 B． n/2 C．n-3 D． 411． 以下说法正确的是 （ ）A． 队列是后进先出B． 栈的特点是后进后出.下载可编辑 .. . . .C． 栈的删除和插入操作都只能在栈顶进行D． 队列的删除和插入操作都只能在队头进行12 . 以下说法不正确的是 （ ）A． 栈的特点是后进先出 B． 队列的特点是先进先出C． 栈的删除操作在栈底进行 ，插入操作在栈顶进行D． 队列的插入操作在队尾进行 ，删除操作在队头进行13． 串函数 StrCmp( “abA”,”aba ”)的值为 （）。
A． 1B． 0C．“abAaba ”D． -114． 一个栈的进栈序列是 a， b， c，d ，则栈的不可能的出栈序列是 （ ）A． adbc B． bcadC． cbad D． dcba15． 设有一个 12 阶的对称矩阵 A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组 b 中（矩阵 A 的第一个元素为 a1,1 ，数组 b 的下标从 1 开始 ），则矩阵 A 中第 4 行的元素在数组 b 中的下标 i 一定有 （ ）A． 7 ≤i≤10 B． 11≤i≤15 C． 9 ≤i≤14 D． 6≤i≤916． 已知一个图的边数为 m ，则该图的所有顶点的度数之和为 （ ）A． 2m B．m C． 2m+1 D． m/217 ． 设有一个带头结点的链队列 ，队列中每个结点由一个数据域 data 和指针域 next 组成， front 和 rear 分别为链队列的头指针和尾指针 ，要执行出队操作 ，用 x 保存出队元素的值 ， p 为指向结点类型的指针 ，可执行如下操作 ： p=front->next;x=p->data; 然后执行（ ）A． front=p->next; B． front->next=p->next;.下载可编辑 .. . . .C． front=p;D． front->next =p;18．以下说法不正确的是 （）。
A． 连通图 G 一定存在生成树B． 连通图 G 的生成树中一定包含G 的所有顶点C． 连通图 G 的生成树中不一定包含G 的所有边D． 连通图 G 的生成树可以是不连通的19．散列查找的原理是 （）A． 在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B． 按待查记录的关键字有序的顺序方式存储C． 按关键字值的比较进行查找D． 基于二分查找的方法20． 空串的长度为 （ ）A．0 B．1 C．2 D．321 ． 排序过程中 ，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置 ，直到全部排好序为止 ，该排序算法是 ( )A． 选择排序 B． 快速排序C． 冒泡排序 D． 直接插入排序22． 采用顺序查找法对长度为 n 的线性表进行查找 （不采用表尾设监视哨的方法 ）， 最坏的情况下要进行 （ ）次元素间的比较 A． n+2 B． n C． n-1 D． n/223． 设有一个 10 阶的对称矩阵 A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组 b 中 矩阵 A 的第一个元素为 a1,1 ，数组 b 的下标从 1 开始）， 则.下载可编辑 .. . . .矩阵元素a5,3 对应一维数组b 的数组元素是 （）。
A． b[18]B． b[8]C． b[13]D． b[10]24．如图 1若从顶点a 出发按广度优先搜索法进行遍历，则可能得到的顶点序列为（ ）A． acebdfghB． aebcghdfab e cC． aedfbcghD． abecdfgh d f g h图 125． 已知如图 2 所示的一个图 ，若从顶点 a 出发 ，按深度优先搜索法进行遍历 ，则可能得到的一种顶点序列为 （ ）A． abecdf B． acfebd C．aebcfd D． aedfcbab e cd f图 2.下载可编辑 .. . . .26． 一棵哈夫曼树总共有 23 个结点 ，该树共有 （ ）个叶结点 （终端结点 ）A． 10 B． 13 C． 11 D． 12二、填空题1． 通常数据的逻辑结构包括集合 、线性 、 _ ___、 _ ___四种类型 2． 通常可以把某城市中各公交站点间的线路图抽象成 ______ __结构 3． 设有一个单向链表 ，结点的指针域为 next ，头指针为 head ， p 指向尾结点 ，为了使该单向链表改为单向循环链表 ，可用语句 ______ __4． 设有一个单向循环链表 ，头指针为 head ，链表中结点的指针域为 next ，p 指向尾结点的直接前驱结点 ，若要删除尾结点 ，得到一个新的单向循环链表 ，可执行操作 ________ 。
5． 循环队列的队头指针为 f，队尾指针为 r，当 时表明队列已空 6． 在一个链队中 ， f 和 r 分别为队头和队尾指针 ，队结点的指针域为 next ，则插入一个 s 所指结点的操作为 _____ ___； r=s ；7． 设有一个链栈 ，栈顶指针为 hs ，现有一个 s 所指向的结点要入栈 ，则可执行操作_______ _ 和 hs=s ；8． 循环队列的队头指针为 f，队尾指针为 r，当 ____ _时表明队列为空 9． 在一个链队中 ， f 和 r 分别为队头和队尾指针 ，队结点的指针域为 next ，则插入一个 s 所指结点的操作为 _____ ___； r=s ；10．“A ”在存储时占 个字节 11． 串的两种最基本的存储方式分别是 _ ______和 ______ __下载可编辑 .. . . .12． 一棵二叉树没有单分支结点 ，有 6 个叶结点 ，则该树总共有 个结点 13． 一棵二叉树中顺序编号为 i 的结点 ，若它存在左 、右孩子 ，则左 、右孩子编号分别为 _____ ___、 ____ ____14 ． 按照二叉树的递归定义 ，对二叉树遍历的常用算法有 __ _ _ 、 ___ _、 ____三种 。
15 ．两个串相等的充分必要条件是 16． 把数据存储到计算机中 ,并具体体现数据之间的逻辑结构称为 结构 17． 一棵二叉树叶结点 （终端结点 ）数为 5，单分支结点数为 2 ，该树共有 ______个结点18． 如图 3 所示的二叉树 ，其后序遍历序列为 ab cd e fhgi。
