下载文档原格式
1．线性链表不具有的特点是（ ).A ．随机访问B ．不必事先估计所需存储空间大小C ．插入与删除时不必移动元素D ．所需空间与线性表长度成正比 2．设一个栈的输入序列为1，2，3，4，则输出序列不可能是( ).A ．1， 2， 3， 4B ．4， 3， 2， 1C ．1， 3， 2, 4D ．4，1,2，33．下列排序算法中,( )排序在每趟结束后不一定能选出一个元素放到其排好序的最终 位置上. A ．归并 B ．冒泡 C ．选择 D ．堆4．下列序列中，（ )是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。
A ．［da, ax ， eb, de, bb ］ ff [ha, gc ］B ．［cd ， eb, ax ， da] ff [ha ， gc, bb ］C ．［gc ， ax, eb, cd, bb] ff ［da ， ha]D ．［ax, bb ， cd ， da] ff [eb ， gc ， ha ］ 5．设有一个10阶的对称矩阵A ［10]［10］，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B ［ ］中，A[0][0］存入B[0］中，则A ［8]［5]在B[ ］中（ ）位置。
A ．32 B ．33 C ．41 D ．65 6。
下面哪一种图的邻接矩阵肯定是对称矩阵（ )。
A ．有向图B ．无向图C ．AOV 网D ．AOE 网 7．具有2008个结点的二叉树，其深度至少为( ）。
A ．9B ．10C ．11D ．12 8. 关键路径是边表示活动的网（AOE 网）中的( ).A ．从源点到汇点的最长路径B ．从源点到汇点的最短路径C ．最长的回路D ．最短的回路9． 一个广义表为（a, (a,b ）， d, e, (（i,j) ,k)），则该广义表的长度为( ). A ．不确定 B ．8 C ．5 D ．610．设循环队列中数组的下标范围是0～n –1，其头尾指针分别为f 和r ，则其元素个数为( ）。
东北农业大学网络教育学院数据结构专升本作业题作业题（一）一、单项选择题1. 从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构2. 链表不具有的特点是（）A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（）。
For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1) B．O(n)C．O(n²) D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。
A．2 B．3C．4 D．65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。
A．98 B．100C．102 D．1066、判定一个栈s（最多元素为m0）为空的条件是（）。
A．s-〉top! =0 B．s-〉top= =0C．s-〉top! =m0 D．s-〉top= =m07、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。
A．（rear-front+m）%m B．rear-front+1C．rear-front-1 D． rear-front8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。
A．连接 B．求子串C．模式匹配 D．判子串9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。
上海海事大学试卷2008—2009(2) 数据结构期终考试 A(试卷编号: 984571) 总计 100 分专业班级学号姓名得分(重要提示:答案必须做在答题纸上,做在试题上不给分)一、单项选择题（本大题共20小题，每小题1分，共20分）1 如果一个栈的进栈序列是ABCD（即，A 先进栈，然后B、C和D依次进栈），允许在进栈过程中可以退栈，且规定每个元素进栈和退栈各一次，那么不可能得到的退栈序列是（）A. DCBAB. ACBDC. DBACD. CDBA2. 先序为a,b,c, 且后序为c,b,a, 的二叉树共有（）棵。
A. 1B. 2C. 3D. 43. 串的长度是（）A. 串中不同字符的个数B. 串中不同字母的个数C. 串中所含字符个数D. 串中所含字符个数且字符个数须大于零4. 设有长度为12的有序表：Apr, Aug, Dec, Feb, Jan, Jul, Jun, Mar, May, Nov, Oct, Sep,按二分查找法查找表内元素Feb所需的查找次数为（）A. 3B. 4C. 5D. 65．设T是一棵二叉树，T中有n 个叶子结点，且非叶子结点都是具有两个孩子的结点，那么T中共有（）个结点。
A. 2n-1B. 2nC. 2n+1D. 2(n+1)6. 对于具有n个结点的顺序存储的线性表，如果采用冒泡排序法进行排序，那么所需要最少的结点比较次数是（）A. n-2B. n-1C. nD. n+17. 在包括有n 个键值的二叉排序树中查找一个键值，在随机的情况下，其平均需要比较次数的数量级为（）A. O(n)B. O(log2n)C. O(n log2n)D. O(n2)8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以9. 数据结构被形式的定义为（K，R），其中K是（）的有限集合，R是K上的关系有限集合。
数据结构求二叉树中叶子结点的个数及二叉树的高度二叉树是一种常用的数据结构，它由若干个节点组成，每个节点最多只有两个子节点：左子节点和右子节点。
二叉树常用来表示树状结构，如文件系统、家族关系等等。
本文将介绍如何求二叉树中叶子节点的个数以及二叉树的高度。
一、求二叉树中叶子节点的个数叶子节点是指没有子节点的节点。
要求二叉树中叶子节点的个数，可以使用递归的方法进行计算。
具体步骤如下：1.判断当前节点是否为空，如果为空，则返回0。
2.判断当前节点是否为叶子节点，如果是，则返回13.否则，递归计算当前节点的左子树中叶子节点的个数和右子树中叶子节点的个数，并将它们相加。
下面是一个示例代码：```pythonclass TreeNode:def __init__(self, value):self.val = valueself.left = Noneself.right = Nonedef get_leaf_nodes_count(root):if root is None:return 0if root.left is None and root.right is None:return 1return get_leaf_nodes_count(root.left) +get_leaf_nodes_count(root.right)```二叉树的高度也可以使用递归的方式进行计算。
根据二叉树的定义，二叉树的高度等于左子树的高度和右子树的高度的较大值，再加1、具体步骤如下：1.判断当前节点是否为空，如果为空，则返回0。
2.计算当前节点的左子树的高度和右子树的高度，取较大值。
3.将较大值加1，即得到当前二叉树的高度。
下面是一个示例代码：```pythondef get_tree_height(root):if root is None:return 0left_height = get_tree_height(root.left)right_height = get_tree_height(root.right)return max(left_height, right_height) + 1```综上所述，本文介绍了如何求二叉树中叶子节点的个数和二叉树的高度。
#include<stdio.h>#include<stdlib.h>#define max 10typedef struct node{char data;node *lchild,*rchild;}Bitree;Bitree *B[max];Bitree *Creatree(){ //建立二叉树Bitree *T,*S;char ch;int front,rear,sign;sign=0;front=0;rear=-1;T=NULL;printf("建立二叉树:\n");ch=getchar();while(ch!='#'){if(ch!='@'){ //输入结点不是虚结点S=(Bitree*)malloc(sizeof(Bitree));S->data=ch;S->lchild=S->rchild=NULL;rear++;B[rear]=S;if(rear==front){T=S;sign++;}else{if(sign%2==1) //寻找父结点B[front]->lchild=S;if(sign%2==0){B[front]->rchild=S;front++;}sign++;}}else{ //输入结点为虚结点if(sign%2==0)front++;sign++;}ch=getchar();}return T;}int Searchleaf(Bitree *T){ //计算叶子数if(T==NULL)return 0;elseif(T->lchild==NULL&&T->rchild==NULL)return 1;elsereturn(Searchleaf(T->lchild)+Searchle af(T->rchild));}void visit(Bitree *T){printf("%c\n",T->data);}void Inorder(Bitree *T){ //中序遍历二叉树if(T!=NULL){Inorder(T->lchild);visit(T);Inorder(T->rchild);}}void main(){Bitree *T;T=Creatree();printf("中序遍历:\n");Inorder(T);printf("叶子数%d\n",Searchleaf(T));}题目：设二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树中叶子结点的数目。
求叶子结点的个数算法叶子结点是二叉树中没有子节点的节点。
在一个二叉树中，叶子结点是没有任何子节点的节点，它们是树的末端节点。
求叶子结点的个数也就是求二叉树中的叶子结点的数量。
要计算叶子结点的个数，我们可以使用递归或迭代的方法。
下面将详细介绍这两种方法。
方法一：递归法递归是从根节点开始一直向下进行的一种算法。
在二叉树问题中，递归可以应用于不断地进入子树的过程。
首先，我们需要定义一个递归函数以计算叶子结点的个数。
该函数的输入参数是当前节点，输出是当前节点及其子树中叶子结点的个数。
算法步骤如下：1.如果当前节点为空，返回0。
2.如果当前节点没有左子树和右子树（即为叶子结点），返回1。
3.递归计算左子树中叶子结点的个数，记为leftCount。
4.递归计算右子树中叶子结点的个数，记为rightCount。
5.返回leftCount + rightCount + 1。
递归算法代码如下：```pythondef countLeaves(root):if root is None:return 0if root.left is None and root.right is None: return 1leftCount = countLeaves(root.left)rightCount = countLeaves(root.right)return leftCount + rightCount```方法二：迭代法迭代法是通过循环处理一系列逻辑步骤以达到解决问题的算法。
对于二叉树问题，迭代法通常需要使用栈或队列来处理树的节点。
我们可以使用深度优先搜索（DFS）的迭代法来计算叶子结点的个数。
算法步骤如下：1.初始化一个栈，并将根节点入栈。
2.初始化叶子结点的数量为0。
3.循环执行以下操作：-从栈中弹出一个节点，并将该节点的子节点入栈。
-如果弹出的节点是叶子结点，则将叶子结点的数量加1。
4.返回叶子结点的数量。
迭代算法代码如下：```pythondef countLeaves(root):if root is None:return 0stack = [root]count = 0while stack:node = stack.pop()if node.left is None and node.right is None: count += 1if node.left:stack.append(node.left)if node.right:stack.append(node.right)return count```以上是求叶子结点的个数的两种常见算法，递归法和迭代法。
吉林省普通高校专升本教育试点考试计算机科学与技术专业综合试卷（数据结构部分共90分）一、填空题（每小题2分，共26分）1. 栈的主要特点是_先进后出_ ；队列的主要特点是__先进先出__ 。
2. 在一长度为n的向量中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动__n-i+1__ 个元素。
3. 对于一个具有n个结点的单链表，在已知P所指结点都插入一个新结点的时间复杂度为__O(1)__ ；在给定值为x的结点后插入一个新结点的时间复杂度为__O(n)___。
4. 设n行n列的下三角矩阵A已压缩到一维数组s[0 … n*(n+1)/2]中，若按行序为主存储，则A[i][j]对应的s中的存储位置为__i(i-1)/2+j-1__ 。
5. 将f=1+1/2+1/3+ … +1/n转化成递归函数，其递归出口是__f(1)=1__，递归体是__f(n)=f(n-1)+1/n___ 。
6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__2h-1__ 。
7. 具有n个叶子结点的哈夫曼树中，其结点总数为__2n-1__ 。
8. 对一个满二叉树，m个树叶，n个结点，深度为h，则n = __2h-1__ 。
9. 判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用__深度优先遍历___ 算法。
10. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是__哈希表查找__ 。
11. 快速排序在最坏情况下的时间复杂度为__O(n2)__ 。
12. 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为_（84，79，56，38，40，46）_ 。
13. 直接存取文件是用__哈希__ 方法组织的。
二、单项选择题（每小题2分，共20分）1. 线性表的顺序存储结构是一种（）的存储结构；线性表的链式存储结构是一种（）的存储结构。
计算二叉树的叶子结点个数 c语言计算二叉树的叶子节点个数二叉树是一种常见的数据结构，它由节点和连接节点的边组成。
在二叉树中，每个节点最多有两个子节点，分别称为左子节点和右子节点。
叶子节点是指没有子节点的节点，也可以称为终端节点。
在计算二叉树的叶子节点个数时，我们需要遍历整个二叉树，统计叶子节点的数量。
为了更好地理解如何计算二叉树的叶子节点个数，我们首先需要了解二叉树的遍历方式。
常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。
在前序遍历中，我们先访问根节点，然后递归地遍历左子树和右子树。
在中序遍历中，我们先递归地遍历左子树，然后访问根节点，最后遍历右子树。
在后序遍历中，我们先递归地遍历左子树和右子树，最后访问根节点。
对于计算二叉树的叶子节点个数，我们可以使用递归的方法。
递归是一种在函数中调用自身的技术。
我们可以定义一个递归函数来计算二叉树的叶子节点个数。
具体的算法如下：1. 如果二叉树为空，则叶子节点个数为0；2. 如果二叉树只有一个节点，则叶子节点个数为1；3. 否则，叶子节点个数等于左子树的叶子节点个数加上右子树的叶子节点个数。
根据上述算法，我们可以编写如下的C语言代码来计算二叉树的叶子节点个数：```c#include <stdio.h>#include <stdlib.h>// 定义二叉树节点的结构体typedef struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right;} TreeNode;// 递归计算二叉树的叶子节点个数int countLeafNodes(TreeNode* root) {// 如果二叉树为空，返回0if (root == NULL) {return 0;}// 如果二叉树只有一个节点，返回1if (root->left == NULL && root->right == NULL) {return 1;}// 递归计算左子树的叶子节点个数int leftCount = countLeafNodes(root->left);// 递归计算右子树的叶子节点个数int rightCount = countLeafNodes(root->right);// 返回左子树和右子树的叶子节点个数之和return leftCount + rightCount;}int main() {// 创建二叉树TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = 1;root->left = (TreeNode*)malloc(sizeof(TreeNode));root->left->val = 2;root->left->left = NULL;root->left->right = NULL;root->right = (TreeNode*)malloc(sizeof(TreeNode));root->right->val = 3;root->right->left = NULL;root->right->right = NULL;// 计算二叉树的叶子节点个数int count = countLeafNodes(root);printf("二叉树的叶子节点个数为：%d\n", count);// 释放二叉树的内存free(root->left);free(root->right);free(root);return 0;}```在上述代码中，我们首先定义了一个二叉树节点的结构体，并且使用malloc函数动态分配了二叉树的内存空间。
沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编附答案最新资料，WORD格式，可编辑修改！目录说明：沈阳师范大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为867计算机学科专业基础综合（数据结构、操作系统），2015年科目代码改为862。
为帮助考生全面复习，特提供2009～2012年408计算机学科专业基础综合真题及详解。
第一部分沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编2014年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题科目代码：867科目名称：计算机学科专业基础综合（数据结构、操作系统）适用专业名称：计算机应用技术考生注意：请将答案写在答题纸上，写在本题签及草纸上无效。
考试后本题签同答题纸一并交回。
一、单项选择题（共10题，每题2分，合计20分）1．某算法的时间复杂度为O(n2)，表明该算法（）。
A．问题规模是n2B．执行时间等于n2C．执行时间与n2成正比D．问题规模与n2成正比2设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实现效率更高。
A．输出第i（1≤i≤n）个元素B．交换第1个元素与第2个元素的值C．顺序输出这n个元素的值D．输出与给定值x相等的元素在线性表中的序号3．给定一个空栈，若10、20、23、13依次进栈，然后有两个数出栈，又有3个数进栈，第一次进栈的23现在在（）。
A．已出栈B．从栈底算起第3个C．栈顶D．从栈底算起第4个4．循环队列qu（其队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置，队列中的单元个数为MaxSize）的队满足条件是（）。
A．（+1）%MaxSize==+1)%MaxSizeB．+1)%MaxSize==+1C．+1)%MaxSize==D．==5．一棵二叉树的中序序列为ABDCEFG，后序序列为BDCAFGE，则其左子树中的节点个数为（）。
