数据结构基础概念试题
数据结构试题
一、单选题
1、在数据结构的讨论中把数据结构从逻辑上分为（C ）
A 内部结构与外部结构
B 静态结构与动态结构
C 线性结构与非线性结构
D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）
A 必须是连续的
B 部分地址必须是连续的
C 一定是不连续的
D 可连续可不连续
3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。
A n
B n/2
C (n-1)/2
D (n+1)/2
4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。
A s→link = p→link; p→link = s;
B p→link = s; s→link = q;
C p→link = s→link; s→link = p;
D q→link = s; s→link = p;
5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。
A 起泡排序
B 堆排序
C 锦标赛排序
D 快速排序
6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。
A 求子串
B 模式匹配
C 串替换
D 串连接
7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j 从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。
A 80
B 100
C 240
D 270
8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。
A 栈
B 队列
C 循环队列
D 优先队列
9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。
A ( front - rear + 1) % m
B ( rear - front + 1) % m
C ( front - rear + m) % m
D ( rear - front + m) % m
11、一个数组元素a[i]与（ A ）的表示等价。
A *（a+i）
B a+i
C *a+i
D &a+i
12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。
A 指针
B 引用
C 值
D 变量
13、下面程序段的时间复杂度为（ C ）
for (int i=0;i for (int j=0;j a[i][j]=i*j; A O(m2) B O(n2) C O(m*n) D O(m+n) 14、下面程序段的时间复杂度为（ B ） int f(unsigned int n) { if(n= =0 || n= =1) return 1; else return n*f(n-1); } A O(1) B O(n) C O(n2) D O(n!) 15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址( D )。 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续或不连续都可以 16、数据结构的定义为(D，S)，其中D是( B )的集合。 A 算法 B数据元素 C 数据操作 D 逻辑结构 17、算法分析的目的是( A )。 A找出数据结构的合理性 B研究算法中输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性 18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B )。 A s->link=p;p->link=s; B s->link=p->link;p->link=s; C s->link=p->link;p=s; D p->link=s;s->link=p; 19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（ B ） A s->link=p->link; p->link=s; B q->link=s; s->link=p C p->link=s->link; s->link=p; D p->link=s; s->link=q; 20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（ A ） A p->link=p->link->link; B p=p->link; p->link=p->link->link; C p->link=p->link; D p=p->link->link; 21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ） A s=rear; rear=rear->link; delete s; B rear=rear->link; delete rear; C rear=rear->link->link; delete rear; D s=rear->link->link; rear->link->link=s->link; delete s; 22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current 为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( D )。 A current->link =null B first->link=current C first=current D current->link=first 23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。 A c,b,a B b,a,c C c,a,b D a,c,b 24、栈的数组表示中，top为栈顶指针，栈空的条件是( A )。 A top=0 B top=maxSize C top=maxSize D top=-1 25、栈和队列的共同特点是( C )。 A 都是先进后出 B 都是先进先出 C只允许在端点处插入和删除 D 没有共同点 26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( D ). A f+1= =r B r+1= =f C f= =0 D f= =r 27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ） A n-2 B n-1 C n D n+1 28、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A top++; B top--; C top=0; D top; 29、设链式栈中结点的结构为（data, link）,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（ A ）操作。 A x=top->data; top=top->link; B top=top->link; x=top->data; C x=top; top=top->link; D x=top->data; 30、设循环队列的结构是： const int Maxsize=100; typedef int Data Type; typedef struct { Data Type data[Maxsize]; Int front, rear; } Queue; 若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（ D ） A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; C Q.front + Q.rear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize; 31、设有一个递归算法如下： int fact (int n ) { if (n<=0) return 1; else return n*fact(n-1); } 下面正确的叙述是（ B ） A 计算fact(n) 需要执行n次递归 B fact(7)=5040 C 此递归算法最多只能计算到fact(8) D 以上结论都不对 32、设有一个递归算法如下 int x (int n) { if (n<=3) return 1; else return x(n-2)+x(n-4)+1; } 试问计算 x(x(8))时需要计算（ D ）次x函数。 A 8 次 B 9 次 C 16 次 D 18次 33、设有广义表D(a,b,D),其长度为（ B ），深度为（ A ） A ∞ B 3 C 2 D 5 34、广义表A(a),则表尾为（ C ） A a B (( ) ) C 空表 D （a） 35、下列广义表是线性表的有（ C ） A E（a,(b,c)） B E(a,E) C E (a,b) D E(a,L( ) ) 36、递归表、再入表、纯表、线性表之间的关系为（ C ） A 再入表>递归表>纯表>线性表 B 递归表>线性表>再入表>纯表 C 递归表>再入表>纯表>线性表 D递归表>再入表>线性表>纯表 37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。 A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子 38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则( A ) A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1 39、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ） A 24 B 73 C 48 D 53 40、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（ A ）。 A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m 41、34 具有35个结点的完全二叉树的深度为( A ) A 5 B 6 C 7 D 8 42、对线性表进行折半搜索时，要求线性表必须（ C ） A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储 C 以数组方式存储且结点按关键码有序排列 D以链接方式存储 43、顺序搜索算法适合于存储结构为（ B ）的线性表。 A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储 44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ） A O（n2） B O（n log2n） C O（log2n） D O（n） 45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A ) A n B n+1 C n-1 D n+e 46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。 A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 深度优先遍历算法 D 广度优先遍历算法 47、在10阶B-树中根结点所包含的关键码个数最多为（C ），最少为( A ) A 1 B 2 C 9 D 10 48、对包含n 个元素的散列表进行搜索，平均搜索长度为（ C ） A O（log2n） B O（n） C 不直接依赖于n D 上述都不对 二、填空题（） 1、数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种 2、数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种 3、一种抽象数据类型包括（数据）和（操作）两个部分。 4、设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配） 5、栈、队列逻辑上都是（线性存储）结构。 6、线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多 对多）的，树形结构中数据元素间的关系是（一对多）的。 7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出） 8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。 9、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第（6）次匹配成功。 10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（ n*i+j）。 11、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素（写）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。 12、在一个循环队列Q中，判断队空的条件为（Q.front= =Q.rear）, 判断队满的条件为（ (Q.rear+1)%MaxSize= =q.front ） 13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ n-1 ）。 14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。 15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（ 2*i+1），右子女结点为（ 2*i+2 ），双亲结点（i>=1 ）为（「(i-1)/2 ┐）. 16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。 17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。 18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字符编码。 19、设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+1 ）个。 20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。 21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。 22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235） 23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。 24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（５），判定树中前５层的结点数为（３１），最后一层的结点数为（１９）。 25、在一个无向图中，所有顶点的度数之和等于所有边数的（２）倍。在一个具有n个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有（ n(n-1) ）条边。 26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）。 27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是( 1044)。 28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。 29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。 30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n） 31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。 32、处理冲突的三种方法，分别为(线性探测)、（随机探测）、（链地址法）。 33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（Ｏ（n2））、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（Ｏ （elog2e）） 34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog2n）），在最坏情况下的时间复杂度为（Ｏ（n2））；快速排序在平均情况下的空间复杂度为（Ｏ（log2n）），在最坏情况下的空间复杂度为（Ｏ（n））。 35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的过程中，第二趟排序后的结果是（［３８４６５６７９］［４０８０］） 36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的第一次划分的结果是（［３８４０］４６［５６７９８０］）。 37、一个结点的子树的（个数）称为该结点的度。度为（零）的结点称为叶结点或终端结点。度不为（零）的结点称为分支结点或非终端结点。树中各结点度的（最大值）称为树的度。 38、设K i=K j (1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中R i领先于R j (i 40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（Ｏ（log2n）），整个排序过程的时间复杂度为（Ｏ（nlog2n））。 41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。 42、假定一个线性表为（”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的 a,b,c三个子表的长度分别为（３），（３），（２）。 43、对于包含５０个关键码的３阶B-树，其最小高度为（４），最大高度为（５）。 44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减１） 45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（５）。 46、在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于（n/m）。 47、在有向图的邻接矩阵中，第i行中“1”的个数是第i个顶点的（出度），第i列中“1”的个数是第i个顶点的（入度）。在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的（度），矩阵中“1”的个数的一半是图中的（边数）。 48、在对m阶B-树中，每个非根结点的关键码数最少为（「m/2┐-1）个，最多为（m-1）个，其子树棵数最少为（「m/2┐），最多为（m）。 三、判断题 1、数据元素是数据的最小单位（╳）。 2、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的(√). 3、数据结构是指相互之间存在一种或多种关系的数据元素的全体（╳）。 4、从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构（√）。 5、线性表的逻辑顺序与物理顺序总是一致的（╳）。 6、二维数组是其数组元素为线性表的线性表（╳）。 7、每种数据结构都应具备三种基本运算：插入、删除、搜索（√）。 8、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（╳） 9、空串与由空格组成的串没有区别。（╳） 10、将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。（√） 11、深度为h的非空二叉树的第h层最多有2h-1个结点（╳） 12、完全二叉树就是满二叉树。（╳） 13、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（√） 14、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。（√） 15、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。（√） 16、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是 该子树的前序遍历结果序列的最后一个结点。（√） 17、任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的 平均搜索时间。（╳） 18、最优二叉搜索树一定是平衡的二叉搜索树。（√） 19、AOE网是一种带权的无环连通图。（√） 20、对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的（╳）。 21、二叉排序树可以是一棵空树（√） 22、线性表中所有结点的类型必须相同。（√） 23、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。（√） 24、任何无环的有向图，其结点都可以排在一个拓扑序列里。（√） 25、队列逻辑上是一个下端口和上端能增加又能减少的线性表（╳） 26、二叉树是树的一种特殊情况（√） 27、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图 中顶点个数有关，而与图的边数无关（√）。 28、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（╳） 29、连通分量是无向图中的极小连通子图。（╳） 30、在ＡＯＥ网络中一定只有一条关键路径。（╳） 31、关键活动不按期完成就会影响整个工程的完成时间。（√） 32、平衡二叉树的左右子树深度之差的绝对值不超过1。（√ ） 33、快速排序是对起泡排序的一种改进。( √ ) 34、直接选择排序稳定。（ ╳ ） 35、堆排序占用的辅助空间很大。（ ╳ ） 36、在散列法中采取开散列法来解决冲突时，其装载因子的取值一定在（０，１）之间。（╳） 37、B-树是一种动态索引结构，它既适用于随机搜索，也适用于顺序搜索。（ ╳） 38、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳） 39、任何一个关键活动延迟，那么整个工程将会延迟。（√） 40、任何一个关键活动提前完成，那么整个工程将会提前完成。（╳） 四、运算应用题 1、在一个有n 个元素的顺序表的第i 个元素（1 ≤ i ≤ n ）之前插入一个新元素时，需要向后移动多少个元素？ 答案：需要向后移动 n- i + 1个元素 2、 当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理 的出栈序列？ 答案： 可能的出栈序列有 种，6457321不是合理的出栈序列。 3、 简单（直接）选择排序是一种稳定的排序方法吗？试举例说明？ 答案：是不稳定的排序方法。下面就是不稳定的例子。只要能举出反例即可。 { 275 275* 512 061 } i = 1 { 061 275* 512 275 } i = 2 { 061 275* 512 275 } i = 3 { 061 275* 275 512 } 4、设有序顺序表为 { 10, 20, 30, 40, 50, 60, 70 }，采用折半搜索时，搜索成功的平均搜索长度是多少？ 答案： ASL succ = (1*1 + 2*2 + 3*4 ) / 7 = 17 / 7 5、 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 答案：结点个数为n 时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n 层；它有1个叶结点，n-1个分支结点。 6、 一棵高度为h 的满k 叉树有如下性质: 第h 层上的结点都是叶结点, 其余各层上每个结点都有k 棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为i 的结点的父结点(若存在)的编号是多少? (3) 编号为i 的结点的第m 个孩子结点(若存在)的编号是多少? (4) 编号为i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? 4291 234567891011121314811717 14=*************=+C (5) 若结点个数为 n, 则高度h是n 的什么函数关系? 答案： （1）各层的结点个数是k i (i=0,1,2,....,h) （2）编号为i的结点的父结点(若存在)的编号是└ (i+k-2)/k」 （3）编号为i的结点的第m个孩子结点(若存在)的编号是(i-1)*k+m+1 （4）当(i-1)%k<>0时有右兄弟，右兄弟的编号为 i+1 （5）若结点个数为 n ，则高度h和n 的关系为：h=log k(n*(k-1)+1)-1 (n=0时h=-1) 7、写出下列中缀表达式的后缀形式： (1) A* - B + C (2) (A + B) * D + E / (F + A * D) + C (3) A && B|| ! (E > F) {注：按C++的优先级) (4) !(A && !( (B < C)||(C > D) ) )||(C < E) 答案：各中缀表达式的后缀形式如下： （1）A B - * C+ (2) A B + D * E F A D * + / + C + (3) A B & & E F > ! | | (4) A B C < C D > | | ! & & ! C E < | | 8、画出下列广义表的图形表示和它们的存储表示： (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) 广义表（2）的图形表示为： 广义表（1）的存储表示为： 广义表（2）的存储表示为： 9、题目：11、将下面的森林变换成二叉树（7分）。 10 7分） 答案： 11、根据所给有向图，写出一个拓扑序列。（5分） 答案： 其中的一个拓扑序列为：V1，V2，V3，V4，V5，V6，V7 12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分） 答案 13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。 答案： 为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有 赫夫曼编码为：概率为0.23的字符编码为：00 概率为0.11的字符编码为：010 概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111 概率为0.29的字符编码为：10 概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110 概率为0.08的字符编码为：1111 14、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图： 15、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。 16、对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL 树, 其最大高度是多少? 最小高度是多少? 答案：设高度为h(空树的高度为-1)的AVL 树的最少结点为N h ，则N h = F h+3 -1。 F h 是斐波那契数。又设AVL 树有n 个结点，则其最大高度不超过3/2*log 2(n+1), 最小高度为「log 2(n+1) ┐-1。 17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 ASL SUCC ASL UNSUCC =1/15（3*1+4*14）=59/15 18、试对下图所示的AOE 网络 (1) 这个工程最早可能在什么时间结束。 (2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。 (3) 求每个活动的最早开始时间e ( )和最迟开始时间l ( )。 (4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。 答案：按拓朴有序的顺序计算各个顶点的最早可能开始时间V e 和最迟允许开始时间V l ，然后再计算各个活动的最早可能开始时间e 和最迟允许开始时间l,根据l-e 是否等于0来确 19、已知有五个待排序的记录，其关键字分别为：256，301，751，129，937,863，742，694，076，438请用快速排序的方法将它们从小到大排列。 答案： 第一次排序：（076，129），256，（751，937，863，742，694，301，439） 第二次排序：076，129，256，（438，301，694，742），751，（863，937） 第三次排序：076，129，256，301，438，（694，742），751，（863，937） 第四次排序：076，129，256，301，438，694，742，751，（863，937） 第五次排序：076，129，256，301，438，694，742，751，863，937 20、设有150个记录要存储到散列表中, 并利用线性探查法解决冲突, 要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？ (设α是散列表的装载因子，则有ASL succ = ( 1+1/ (1-α) )/2)。 答案：已知要存储的记录数为n=150,查找成功的平均查找长度为ASL succ ≤2，则有：ASL succ =1/2（1+1/（1-α））≤2 解得α≤2/3 ，又有：α=n/m=150/m 两式联立得：150/m≤2/3,解得：m≥225. 所以散列表需要设计225个单位。 它的关键码。如满足上述条件，则是二叉搜索树。 概念结构设计和逻辑结构设计 一.系统概述 本系统通过调查从事医药产品的零售，批发等工作的企业，根据其具体情况设计医药销售管理系统。医药管理系统的设计和制作需要建立在调查的数据基础上，系统完成后预期希望实现药品基本信息的处理，辅助个部门工作人员工作并记录一些信息，一便于药品的销售和管理。通过此系统的功能，从事药品零售和批发等部门可以实现一些功能，如：基础信息管理，进货管理，库房管理，销售管理，财务统计，系统维护等。 二．概念结构设计 1.员工属性 2.药品属性 3.客户属性 4.供应商属性 5.医药销售管理系统E--R 图 三．逻辑结构设计 该设计概念以概念结构设计中的E--R 图为主要依据，设计出相关的整体逻辑结构，具体关系模型如下：（加下划线的表示为主码） 药品信息（药品编号，药品名称，药品类别，规格，售价，进价，有效期，生产日期，产地，备注） 供应商信息（供应商编号，供应商名称，负责人，） 员工 姓名 家庭地址 E-maill 电话 员工 编号 年龄 帐号 四．系统各功能模块如何现（数据流实图）；1.基本信息管理子系统 基本信息管理子系统 药品信息员工信息客户信息供应商信息2.库存管理子系统 库存管理子系 统 库存查询库存信息出入库登记库存报表3.销售管理子系统 销售管理 销售登记销售退货销售查询 4.信息预警子系统 信息预警 报废预警库存预警 5.财务统计子系统 财务统计 统计销售额打印报表 6.系统管理子系统 系统管理 权限管理修改密码系统帮助 五．数据库设计（E-R图，数据库表结构） 1.药品基本信息表 列名字段数据类型可否为空说明药品编号 药品名称 药品类别 规格 进价 有效期 生产日期 售价 产地 备注 2.员工基本信息表 列名字段数据类型可否为空说明员工编号 性别 身份证号 员工年龄 不定项选择题（针对以下题目，请选择最符合题目要求的答案，每道题有一项或二项正确答案。针对每一道题目，所有答案都选对，则该题得分，所选答案错误或不能选出所有答案，则该题不得分。题量为50道，每题2分，总分为100分。） 第一章 1、是SQLServer数据库的主数据文件的扩展名。（选择一项） A、.sql B、.mdb C、.ldf D、.mdf 2、在SQL Server 2005中，有系统数据库和用户数据库，下列不属于系统数据库的是（）。 （选择一项） A、master B、pubs C、model D、msdb 3、当安装完SQL Server2005数据库时,系统默认当前的超级管理员是( ) （选择一项） A、sa B、master C、administrator D、super 4、在使用SQL Server2005数据库时，有时需要将本机的数据库移动到其他机器上，恢复成对应的数据库使用。移动数据库分两步进行，应包括（）和附加数据库（选择一项）A、分离数据库 B、删除数据库 C、新建数据库 D、合并数据库 5、在SQL Server2005中，附加数据库操作是指（）（选择一项） A、把SQL Server 数据库文件保存为其他数据文件 B、根据数据库物理文件中的信息，把数据库在SQL Server 2005中恢复 C、把所有该数据库表的数据清空 D、把数据库删除掉 6、某单位由不同的部门组成，不同的部门每天都会生产一些报告、报表等数据，以为都采用纸张的形式来进行数据的保存和分类，随着业务的发展，这些数据越来越多，管理这些报告越来越费力，此时应考虑（）（选择一项） A、由多个人来完成这些工作 B、在不同的部门中，由专门的人员去管理这些数据 C、采用数据库系统来管理这些数据 D、把这些数据统一成一样的格式 7、在SQL Server 2005中，对于数据库的定义正确的是（）（选择一项） A、数据库是用来描述事物的符号记录 B、数据库是位于用户与操作系统之间的一层数据管理软件 实用标准文档 文案大全第1章数据结构基础 结构之美无处不在： 说到结构，任何一件事物都有自己的结构，就如可以看得见且触摸得到的课桌、椅子，还有看不见却也存在的化学中的分子、原子。可见，一件事物只要存在，就一定会有自己的结构。一幅画的生成，作家在挥毫泼墨之前，首先要在数尺素绢之上做结构上的统筹规划、谋篇布局。一件衣服的制作，如果在制作之前没有对衣服的袖、领、肩、襟、身等各个部位周密筹划，形成一个合理的结构系统，便无法缝制出合体的衣服。还有教育管理系统的结构、通用技术的学科结构和课堂教学结构等。试想一下，管理大量数据是否也需要用到数据结构呢？ 本章知识要点： 数据结构的基本概念 数据类型和抽象数据类型 算法和算法分析 1.1 数据结构的基本概念 计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算，还是数据处理、过程控制、对文件的存储和检索以及数据库技术等计算机应用，都是对数据进行加工处理的过程。因此，要设计出一个结构良好而且效率较高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。 计算机在发展的初期，其应用围是数值计算，所处理的数据都是整型、实型和布尔型等简单数据，以此为加工、处理对象的程序设计称为数值型程序设计。随着计算技术的发展，计算机逐渐进入到商业、制造业等其他领域，广泛地应用于数据处理和过程控制中。与此相对应，计算机所处理的数据也不再是简单的数值，而是字符串、图形、图像、语音和视频等复杂的数据。这些复杂的数据不仅量大，而且具有一定的结构。例如，一幅图像是一个由简单数值组成的矩阵，一个图形中的几何坐标可以组成表。此外，语言编译过程 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为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)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 Access2010《数据库基本知识》综合练习试题 (共有 37 题; 满分: 39 分; 总时; 80 分钟) 第1 题: (单选题, 1 分) 下面关于关系叙述中，错误的是_____。 A．一个关系是一张二维表 B．二维表一定是关系 C．有的二维表不是关系 D．同一列只能出自同一个域 [A]选A [B]选B [C]选C [D]选D 答案: B 第2 题: (单选题, 1 分) 在E-R图中，用来表示实体之间联系的图形是_____。 A．椭圆形 B．矩形 C．三角形 D．菱形 [A]选A [B]选B [C]选C [D]选D 答案: D 第3 题: (单选题, 1 分) 下列实体的联系中，属于多对多的联系是_____。 A．工厂与厂长 B．工厂与车间 C．车间与车间主任 D．读者与图书馆图书 [A]选A [B]选B [C]选C [D]选D 答案: D 第4 题: (单选题, 1 分) 假定有关系模式：部门(部门号，部门名称)，职工(职工号，姓名，性别，职称，部门号)，工资(职工号，基本工资，奖金)，级别(职称，对应行政级别)，要查找在“财务部”工作的职工的姓名及奖金，将涉及的关系是_____。 A．职工，工资 B．职工，部门 C．部门，级别，工资 D．职工，工资，部门 [A]选A [B]选B [C]选C [D]选D 答案: D 第5 题: (单选题, 1 分) 在Access表中，可以定义3种主关键字，它们是_____。 A. 单字段、双字段和多字段 B. 单字段、双字段和自动编号 C. 单字段、多字段和自动编号 D. 双字段、多字段和自动编号 [A]选A [B]选B [C]选C [D]选D 答案: C 第6 题: (单选题, 1 分) 在打开某个Access2010 数据库后，双击“导航窗格”上的表对象列表中的某个表名，便可打开该表的_________。 A．关系视图 B．查询视图 C．设计视图 D．数据表视图 [A]选A [B]选B [C]选C [D]选D 答案: D 第7 题: (单选题, 1 分) 对于Access2010 数据库，在下列数据类型中，不可以设置“字段大小”属性的是_______。 A．文本 B．数字 C．备注 D．自动编号（分长整、同步复制ID） [A]选A [B]选B [C]选C [D]选D 答案: C 第8 题: (单选题, 1 分) 在表设计视图中，若要将某个表中的若干个字段定义为主键，需要先按住_____键， 逐个单击所需字段后，再单击“主键”按钮。 A．Shift B．Ctrl C．Alt D．Tab [A]选A [B]选B [C]选C [D]选D 答案: B 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 第1题: 委托开发的一个关键问题是要解决技术人员与企业的业务人员之间的沟通问题。对 第2题: 以信息资源的开发与利用为中心的信息管理强调以计算机技术为核心，以管理信息系统为主要阵地，以解决大量数据处理和检索问题为主要任务。不对 第3题: 根据信息技术扩散模型，在集成阶段，企业通过总结经验教训，开始认识到运用系统的方法，从总体出发，全面规划，进行信息系统的建设与改造。不对 第4题: 对于企业信息化的发展阶段，不同的学者有不同的论述，建立了不同的模型。比较著名的模型有两个，一个是世界银行报告中提出的信息技术的扩散模型，另一个是诺兰模型。对 第5题: 战略目标集转化法虽然也首先强调目标，但它没有明显的目标导引过程。它通过识别企业“过程”引出了系统目标，企业目标到系统目标的转换是通过企业过程／数据类矩阵的分析得到的。不对第6题: 生命周期法按用户至上的原则，严格区分工作阶段，整个开发过程工程化。对 第7题: 原型法充分利用最新的软件工具很快形成原型。一方面，将系统调查、系统分析、系统设计三个阶段融为一体，缩短了开发周期。对 第8题: 在管理信息系统的分析过程中，通过制作业务过程和数据的U/C矩阵可以帮助我们合理划分系统逻辑功能（即：系统功能模块的划分）。对 第9题: 对于企业来说管理信息系统只存在有无的问题，并无优劣之分。不对 第10题: 管理信息系统纯粹是一个技术系统，人的作用只是微乎其微。不对 第11题: 管理信息系统由信息的采集、信息的传递、信息的储存、信息的加工、信息的维护和信息的使用五个方面组成。对 第12题: 管理信息系统从概念上看由四大部件组成：信息源、信息处理器、信息用户和信息管理者。对 第13题: 管理信息系统能提供信息，具有支持企业或组织的运行、管理和记录功能。对 第14题: 管理信息系统很难实测企业的各种运行情况。不对 第15题: 管理信息系统的特点是必须通过传统物流服务方式才能实现信息传递。不对 第16题: 在信息管理中, 信息和数据是两个在概念上有所区别的术语，所以任何时候针对任何对象，信息和数据都是绝对而言的，不能混淆。不对 第17题: 在对这些信息的加工中，按处理功能的高低可把加工分为预加工、综合分析和决策处理。对 第18题: 许多企业都能从记录到的客户销售数据中经过仔细分析得到潜在的客户需求并极力追求进一步的市场份额，这说明了信息系统可以改进企业的生产销售方式。对 第19题: 管理信息系统是仅仅服务于管理控制层的信息系统，所以从广义上，MIS对各个子系统具有管理、控制、计划的功能。不对 第20题: 根据诺兰模型，在信息管理阶段，信息系统面向企业整个管理层次，从低层的事务处理到高层的预测与决策都能提供信息支持。对 第21题: 划分时应同时遵循两点原则：沿对角线一个接一个地画小方块，即不能重叠，又不能漏掉任何一个数据和过程；小方块的划分是任意的，但必须将所有的“C”元素都包含在小方块内。对 第22题: 对于有关产品和服务的活动在定义企业过程时应收集有关资料，和有经验的管理人员讨论、分析、研究，确定企业战略规划和管理控制方面的过程。不对 第23题: 由E-R图导出关系数据模型时，如两实体间是1：n联系，应把一方实体的关键字纳入另一方实体的关系中，同时把联系的属性也一并纳入另一方的关系中。不对 第24题: 项目质量管理是指为使项目能达到用户满意的预先规定的质量要求和标准所进行的一系列管理与控制工作。包括进行质量规划，安排质量保证措施，设定质量控制点，对每项活动进行质量检查和控制等。对 第25题: CIO是从企业的全局和整体需要出发，直接领导与主持全企业的信息资源管理工作的企业高层管理人员。CIO产生于信息管理发展的竞争情报阶段。对 第26题: 对信息资源进行有效管理,不仅要考虑信息系统的输入部分和输出部分,更应该重视将输入数据转换成输出信息的信息处理部分。对 《数据结构》基本概念 基本概念 ?数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 ?数据元素 数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 ?数据项 数据项是构成数据元素的不可分割的最小单位。?数据对象 数据对象是具有相同性质的数据元素的集合，是数据的子集。 注意：在不产生混淆的情况下，将数据对象简称为数据。 ?数据结构 数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = (D, R)，其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 ?数据的逻辑结构 数据的逻辑结构是指数据元素之间逻辑关系的整体。 根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵线性结构：数据元素之间存在着一对一的线性关系； ⑶树结构：数据元素之间存在着一对多的层次关系； ⑷图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。?数据的存储结构 数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 ?抽象数据类型 抽象数据类型是一个数据结构以及定义在该结构上 《数据结构基础教程》习题解答(新) 第1章习题解答 一、填空 1.数据就是指所有能够输入到计算机中被计算机加工、处理得符号得集合。 2.可以把计算机处理得数据,笼统地分成数值型与非数值型两大类。 3.数据得逻辑结构就就是指数据间得邻接关系。 4.数据就是由一个个数据元素集合而成得。 5.数据项就是数据元素中不可再分割得最小标识单位,通常不具备完整、确定得实际意义,只就是反映数据元素某一方面得属性。 6.数据就是以数据元素为单位存放在内存得,分配给它得内存区域称为存储结点。 7.每个数据元素都具有完整、确定得实际意义,就是数据加工处理得对象。 8.如果两个数据结点之间有着逻辑上得某种关系,那么就称这两个结点就是邻接得。 9.在一个存储结点里,除了要有数据本身得内容外,还要有体现数据间邻接关系得内容。 10.从整体上瞧,数据在存储器内有两种存放得方式:一就是集中存放在一个连续得内存存储区中;一就是利用存储器中得零星区域, 分散地存放在内存得各个地方。 11.在有些书里,数据得“存储结构”也称为数据得“物理结构”。 12.“基本操作”就是指算法中那种所需时间与操作数得具体取值无关得操作。 二、选择 1.在常见得数据处理中, B 就是最基本得处理。 A.删除 B.查找 C.读取 D.插入 2.下面给出得名称中, A 不就是数据元素得同义词。 A.字段 B.结点 C.顶点 D.记录 3. D 就是图状关系得特例。 A.只有线性关系 B.只有树型关系 C.线性关系与树型关系都不 D.线性关系与树型关系都 4.链式存储结构中,每个数据得存储结点里 D指向邻接存储结点得指针,用以反映数据间得逻辑关系。 A.只能有1个 B.只能有2个 C.只能有3个 D.可以有多个 5.本书将采用 C 来描述算法。 A.自然语言 B.流程图(即框图) C.类C语言 D.C语言 6.有下面得算法段: for (i=0; i /** *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。 *15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种双向、对称的结构。 *16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链表形成next链环和prior链环。 *17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1，而链表的存储密度小于1。 *18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。 *19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。 *20、顺序栈：采用顺序存储结构的栈，称为顺序栈。 *21、链栈：采用链式存储结构的栈，称为链栈。 *22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。 *24、顺序队列：采用顺序存储结构的队列，称为顺序队列。 *25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环， 基本概念 数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号 集合。 数据元素数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项 数据项是构成数据元素的不可分割的最小单位。 数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。注意：在不产生混淆的情况下，将数据对象简称为数据。 数据结构数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = （D, R），其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 数据的逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴ 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵ 线性结构：数据元素之间存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在着一对多的层次关系； ⑷ 图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。 数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 抽象数据类型抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实现两个不同的视图，实现了封装和信息隐藏。 算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法的特性 ⑴ 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。 ⑵ 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。 ⑶ 有穷性：一个算法必须总是(对任何合法的输入)在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 线性表的定义 线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度，长度等于零时称为空表。 线性表的逻辑关系 在一个非空表L= (a i, a2, , a n)中，任意一对相邻的数据元素和a i之间(1< i < n)存在序偶 关系(a i-i，a i)，且a i-i称为a i的前驱，a i称为的后继。在这个序列中，a i无前驱，a n无后继，其它每个元素有且仅有一个前驱和一个后继。 顺序表的存储结构定义 用MaxSize 表示数组的长度,顺序表的存储结构定义如下： #define MaxSize i00 typedef struct { ElemType data[MaxSize]; // ElemType 表示不确定的数据类型 int length; //length 表示线性表的长度 一、判断题 （第一章绪论） 1.数据元素是数据的最小单元。 答案：错误 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。 答案：错误 3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。 答案：正确 4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。 答案：错误 5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间 答案：正确 （第二章线性表） 6.取顺序存储线性表的第i个元素的时间同i的大小有关。 答案：错误 7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 答案：正确 8.线性链表的每一个节点都恰好包含一个指针域。 答案：错误 9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。 答案：正确 10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。答案：错误 （第三章栈） 11.栈是一种对进栈和出栈作了限制的线性表。 答案：错误 12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。答案：错误 13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。 答案：正确 14.空栈就是所有元素都为0上的栈。 答案：错误 15.将十进制数转换为二进制数是栈的典型应用之一。 答案：正确 （第四章队列） 16.队列式限制在两端进行操作的线性表。 答案：正确 17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。 答案：错误 18.在循环链列队中无溢出现像。 答案：错误 19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。 答案：正确 20.顺序队列和循环队列关于队满和队空的判断条件是一样的。 答案：错误 （第五章串） 21.串是n个字母的有限序列。 答案：错误 22.串的堆分配存储是一种动态存储结构。 数据结构基础知识整理 *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数 据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或 多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而 实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结 数据库基础知识试题 部门____________ 姓名__________ 日期_________ 得分__________ 一、不定项选择题（每题分，共30分） 1.DELETE语句用来删除表中的数据,一次可以删除( )。D A .一行 B.多行 C.一行和多行 D.多行 2.数据库文件中主数据文件扩展名和次数据库文件扩展名分别为( )。C A. .mdf .ldf B. .ldf .mdf C. .mdf .ndf D. .ndf .mdf 3.视图是从一个或多个表中或视图中导出的（）。A A 表 B 查询 C 报表 D 数据 4.下列运算符中表示任意字符的是( )。B A. * B. % C. LIKE 5.（）是SQL Server中最重要的管理工具。A A．企业管理器 B.查询分析器 C.服务管理器 D.事件探察器 6.（）不是用来查询、添加、修改和删除数据库中数据的语句。D A、SELECT B、INSERT C、UPDATE D、DROP 7.在oracle中下列哪个表名是不允许的（）。D A、abc$ B、abc C、abc_ D、_abc 8.使用SQL命令将教师表teacher中工资salary字段的值增加500，应该使用的命令 是（）。D A、Replace salary with salary+500 B、Update teacher salary with salary+500 C、Update set salary with salary+500 D、Update teacher set salary=salary+500 9.表的两种相关约束是（）。C 单元练习1 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳ ) (√)(1)数据的逻辑结构与数据元素本身的内容与形式无关。 (√)(2)一个数据结构就是由一个逻辑结构与这个逻辑结构上的一个基本运算集构成的整体。 (ㄨ)(3)数据元素就是数据的最小单位。 (ㄨ)(4)数据的逻辑结构与数据的存储结构就是相同的。 (ㄨ)(5)程序与算法原则上没有区别,所以在讨论数据结构时可以通用。 (√)(6)从逻辑关系上讲,数据结构主要分为线性结构与非线性结构两类。 (√)(7)数据的存储结构就是数据的逻辑结构的存储映像。 (√)(8)数据的物理结构就是指数据在计算机内实际的存储形式。 (ㄨ)(9)数据的逻辑结构就是依赖于计算机的。 (√)(10)算法就是对解题方法与步骤的描述。 二.填空题 （1）数据有逻辑结构与存储结构两种结构。 （2）数据逻辑结构除了集合以外,还包括:线性结构、树形结构与图形结构。（3）数据结构按逻辑结构可分为两大类,它们就是线性结构与非线性结构。（4）树形结构与图形结构合称为非线性结构。 （5）在树形结构中,除了树根结点以外,其余每个结点只有 1 个前趋结点。 （6）在图形结构中,每个结点的前趋结点数与后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括:顺序存储、链式存储、索引存储与散列存储。（9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系, （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构与算法(或运算) 三个方面的内容。 （13）数据结构被定义为(D,R),其中D就是数据的有限集合,R就是D上的关系的有限集合。 （14）算法就是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法与事后统计法。 （16）一个算法的时间复杂性就是算法输入规模的函数。 （17）算法的空间复杂度就是指该算法所耗费的存储空间 ,它就是该算法求解问题规模n的函数。 （18）若一个算法中的语句频度之与为T(n)=6n+3nlog2n,则算法的时间复杂度为O(nlog2n) 。 数据结构基本知识 数据（Data） 数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括： 整数、实数、字符串、图像和声音等。 数据元素（Data Element） 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。 一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。 数据项是具有独立含义的最小标识单位。 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 1．数据结构一般包括以下三方面内容： ①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）； 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）； 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 ③数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的 检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。 为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。 【例1．1】学生成绩表，见下表。 注意：在表中指出数据元素、数据项、开始结点和终端结点等概念 （1）逻辑结构 表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。 表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。 7.3 概念结构设计 将需求分析得到的用户需求抽象为信息结构即概念模型的过程就是概念结构设计。它是整个数据库设计的关键。(概念结构是对用户需求的客观反映，不涉及到软硬件环境，也不能直接在数据库管理系统DBMS上实现，是现实世界与机器世界的中介。这一阶段所产生的工作结果一般表现为E-R图的形式，它不仅能够充分反映客观世界，而且易于非计算机人员理解，易于向关系、网状、层次等各种数据模型转换。) 7.3.1 概念结构 在需求分析阶段所得到的应用需求应该首先抽象为信息世界的结构，才能更好地、更准确地用某一DBMS实现这些需求。 概念结构的主要特点是: (1) 能真实、充分地反映现实世界，包括事物和事物之间的联系，能满足用户对数据的处理要求。是对现实世界的一个真实模型。 (2) 易于理解，从而可以用它和不熟悉计算机的用户交换意见，用户的积极参与是数据库的设计成功的关键。 (3) 易于更改，当应用环境和应用要求改变时，容易对概念模型修改和扩充。 (4) 易于向关系、网状、层次等各种数据模型转换。 概念结构是各种数据模型的共同基础，它比数据模型更独立于机器、更抽象，从而更加稳定。 描述概念模型的有力工具是E-R模型。有关E-R模型的基本概念已在第一章介绍。下面将用E-R模型来描述概念结构。 7.3.2 概念结构设计的方法与步骤 设计概念结构通常有四类方法: ·自顶向下。即首先定义全局概念结构的框架，然后逐步细化，如图7.7(a)所示。 ·自底向上。即首先定义各局部应用的概念结构，然后将它们集成起来，得到全局概念结构，如图7.7（b）所示。 ·逐步扩张。首先定义最重要的核心概念结构，然后向外扩充，以滚雪球的方式逐步生成其他概念结构，直至总体概念结构，如图7.7(c)所示。 ·混合策略。即将自顶向下和自底向上相结合，用自顶向下策略设计一个全局概念结构的框架，以它为骨架集成由自底向上策略中设计的各局部概念结构。 其中最经常采用的策略是自底向上方法。即自顶向下地进行需求分析，然后再自底向上地设计概念结构。如图7.8所示。这里只介绍自底向上设计概念结构的方法。它通常分为两步:第1步是抽象数据并设计局部视图，第2步是集成局部视图，得到全局的概念结构，如图7.9所示。概念结构设计和逻辑结构设计
sql数据库基础面试题复习试题考试题_全
大数据结构的基本概念
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
数据结构与算法基础知识总结
Access2010《数据库基本知识》综合练习试题
(完整版)非常实用的数据结构知识点总结
数据库基础与应用试题与答案(1)
《数据结构》基本概念
《数据结构基础教程》习题及解答
数据结构基础知识大全
《数据结构》基本概念
实用数据结构基础(第四版)课后习题知识讲解
数据结构基础知识整理
数据库基础知识试题(含答案)
实用数据结构基础参考答案
数据结构基本知识.
7.3 概念结构设计(S)