数据结构练习题及答案


    数结构练题答案
    第1章 绪
    判断题
    1 数逻辑结构数元素身容形式关 (√)
    2 数结构逻辑结构逻辑结构基运算集构成整体 (√)
    3 数元素数单位 (×)
    4 数逻辑结构数存储结构相 (×)
    5 程序算法原没区讨数结构时通 (×)
    6 逻辑关系讲数结构分线性结构非线性结构两类 (√)
    7 数存储结构数逻辑结构存储映象 (√)
    8 数物理结构指数计算机实际存储形式 (√)
    9 数逻辑结构赖计算机 (×)
    10 算法解题方法步骤描述 (√)
    二填空题
    1 数逻辑结构 存储结构 两种结构
    2 数逻辑结构集合外包括线性结构树形结构图形结构
    3 数结构逻辑结构分两类线性结构非线性结构
    4 树形结构 图形结构 合称非线性结构
    5 树形结构中树根结点外余结点1前驱结点
    6 图形结构中结点前驱结点数继结点数意
    7 数存储结构物理结构
    8 数存储结构形式包括序存储链式存储索引存储散列存储
    9 线性结构中元素间存 关系
    10 树形结构中元素间存 关系
    11 图形结构元素间存 关系
    12 数结构研究数逻辑结构存储结构算法(运算) 3方面容
    13 数结构定义(DR)中D数限集合RD关系 限集合
    14 算法穷指令 集合
    15 算法效率度量分事先估算法事统计法
    16 算法时间复杂度算法 输入规模 函数
    17 算法空间复杂度指该算法耗费存储空间 该算法求解问题规模n函数
    18 算法中语句频度T(n)6n+3nlog2n算法时间复杂度O( nlog2n)
    19 算法语句频度T(n)3n+nlog2+n2算法时间复杂度O(n2)
    20 数结构门研究非数值计算程序问题中计算机操作象间关系运算学科
    三选择题
    1 数结构通常研究数(A)间相互关系
    A.存储结构逻辑结构 B.存储抽象 C.联系抽象 D.联系逻辑
    2 逻辑数结构分成(C)
    A.动态结构静态结构 B.紧凑结构非紧凑结构
    C.线性结构非线性结构 D.部结构外部结构
    3 数计算机存储表示时物理址逻辑址相连续称(C)
    A.存储结构 B.逻辑结构 C.序存储结构 D.链式存储结构
    4 非线性结构中结点(D)
    A.直接前驱结点. B.直接继结点.
    C.直接前驱结点直接继结点D.直接前驱结点直接继结点
    5 链式存储结构占存储空间(A)
    A.分两部分部分存放结点值部分存放表示结点间关系指针
    B.部分存放结点值 C.部分存储表示结点间关系指针
    D.分两部分部分存放结点值部分存放结点占单元素
    6 算法计算量称算法(C)
    A.现实性 B.难度 C.时间复杂性 D.效率
    7 数基单位(B)
    A.数结构 B.数元素 C.数项 D.文件
    8 结点含数元素存储结点相继存放连续存储空间里种存储结构称(A)结构
    A.序结构 B.链式结构 C.索引结构 D.散列结构
    9 存储结点仅含数元素包含组指针该存储方式(B)
    A.序 B.链式 C.索引 D.散列
    10 两结点间没逻辑关系(D)
    A.图形结构 B.线性结构 C.树形结构 D.集合
    11 数结构中计算机关(C)
    A.物理结构 B.存储结构 C.逻辑结构 D.逻辑存储结构
    12 列4种基逻辑结构中数元素间关系弱(A)
    A.集合 B.线性结构 C.树形结构 D.图形结构
    13 数元素身形式容相位置数关数(A)
    A.逻辑结构 B.存储结构 C.逻辑实现 D.存储实现
    14 存储结点含数元素存储结点存放连续存储空间外组指明结点存储位置表该存储方式(C)存储方式
    A.序 B.链式 C.索引 D.散列
    15 算法正确实现预定功特性称算法(A)
    A.正确性 B.易读性 C.健壮性 D.高效性
    16 算法发生非法操作时作出相应处理特性称算法(C)
    A.正确性 B.易读性 C.健壮性 D.高效性
    17 列时间复杂度中坏(D)
    A.O(1) BO(n) CO( log2n) DO(n2)
    18 列算法时间复杂度(D)
    for(i0ifor(joi c[i][j]i+j
    A.O(1) BO(n) C( log2n) DO(n2)
    19 算法分析两方面(A)
    A空间复杂性时间复杂性 B正确性简明性
    C读性文档性 D数复杂性程序复杂性
    20 计算机算法必须具备输入输出(C)
    A计算方法 B排序方法 C解决问题限运算步骤D程序设计方法
    第2章 线性表
    判断题
    1 线性表链式存储结构优序存储 (×)
    2 链表结点恰包含指针域 (×)
    3 线性表链式存储结构中逻辑相邻两元素物理位置定紧邻 (√)
    4 序存储方式优点存储密度插入删效率高 (×)
    5 线性链表删算法简单删链中某结点计算机会动续单元前移动 (×)
    6 序表结点简单类型链表结点复杂类型 (×)
    7 线性表链式存储特点组意存储单元存储表中数元素 (√)
    8 线性表采序存储必须占片连续存储单元 (√)
    9 序表结构适宜进行序存取链表适宜进行机存取 (×)
    10 插入删操作数结构中基两种操作两种操作数组中常(×)
    二填空题
    1 序表中逻辑相邻元素物理位置必须相邻
    2 线性表中结点集合限结点间关系关系
    3 序表相链表优点节省存储机存取
    4 链表相序表优点插入删方便
    5 线性表元素总数基稳定少进行插入删操作求快速度存取线性表中元素时应采 序 存储结构
    6 序表中访问意结点时间复杂度均O(1)
    7 链表相序表优点插入删方便缺点存储密度
    8 双链表中删已知结点*P时间复杂度O(1)
    9 单链表中已知结点*P前插入新结点需找*P直接前驱结点址查找时间复杂度O(n)
    10 单链表中需知道头指针遍历整链表
    11 线性表中第结点没直接前驱称开始结点
    12 长度n序表中删第i元素移动 ni 元素
    13 长度n序表中果第i元素前插入元素移 ni+1 元素
    14 头结点单链表中第结点址存放头指针中结点存储址存放
    前趋 结点指针域中
    15 线性表元素总数确定常需进行插入删操作应采 链子 存储结构
    16 线性表中链式存储中元素间逻辑关系通 指针 决定
    17 双链表中结点两指针域指 前趋 结点指继结点
    18 需常进行插入删操作线性表采 链式 存储结构宜
    19 双链表中设P指中删结点需执行操作p>prior>nextp>nextp>next>priorp>prior
    20 图示链表中指针P结点插入数域值ab两结点语句S>next>nextp>nextP> nextS实现该操作




    p



    a b

    s
    三 选择题
    1 具n结点单链表中实现( A)操作算法时间复杂度O(n)
    A遍历链表求链表第i结点 B址P结点插入结点
    C删开始结点 D删址P结点继结点
    2 设abc3结点p1020分代表址存储结构称( B )

    p a 10 b 20 c ∧

    A.循环链表 B.单链表 C.双循环链表 D.双链表
    3 单链表存储密度( C )
    A1 B等1 C1 D确定
    4 已知序存储线性表设结点占m存储单元第结点址B第i结点址( A )
    AB+(i1)×m BB+i×m CBi×m DB+(i+1)×m
    5 n结点序表做插入删结点运算时间复杂度( B )
    A.O(1) BO(n) C O(n2) DO( log2n)
    6 设frontrear分循环双链表结点左指针右指针指针P指元素双循环链表L尾元素条件( D )
    AP L BP>front L CP NULL DP>rear L
    7 两指针PQ分指单链表两元素P指元素Q指元素前驱条件( B )
    A.P>next Q>next BP>next Q CQ>next P DPQ
    8 链表存储线性表优点( C )
    A.便机存取 B.花费存储空间序表少
    C.便插入删 D.数元素物理序逻辑序相
    9 单链表中增加头结点目( C )
    A.单链表少结点 B.标志表中首结点位置
    C.方便运算实现 D.说明该单链表线性表链式存储结构
    10 面关线性表叙述中错误( D )关系
    A.序表必须占片址连续存储单元B.序表机存取元素
    C.链表必占片址连续存储单元D.链表机存取元素
    11 L线性表已知LengthList(L)值5DelList(L2)运算LengthList(L)值( C )
    A.2 B.3 C.4 D.5
    12 单链表示意图:
    L
    A B C D ∧

    P Q R
    指链表Q结点前驱指针( B )
    A.L B.P C.Q D.R
    13 设p指单循环链表某结点指针*p直接前驱( C )
    A.找 B.查找时间复杂度O(1)
    C.查找时间复杂度O(n)D.查找结点次数约n
    14 等概率情况n结点序表做插入结点运算需均移动结点数目( 8 )
    A.n B(n1)2 Cn2 D(n+1)2
    15 列链表中前结点出发访问余结点( C )
    A双链表 B单循环链表 C单链表 D双循环链表
    16 序表中知道( D )求出结点存储址
    A基址 B结点 C量 D基址结点
    17 双链表中做插入运算时间复杂度( A )
    A.O(1) BO(n) C O(n2) DO( log2n)
    18 链表具备特点( A )
    A.机访问 B必事先估计存储空间C 插入删时需移动元素 D需空间线性表成正
    19 关线性表述正确( C )
    A线性表中元素数字字符记录等类型B线性序表中包含元素数意
    C线性表中结点仅直接前驱直接继
    D存样线性表表中没结点
    20 ( B )运算中序表链表
    A插入 B根序号查找 C删 D根元素查找
    第3章 栈
    判断题
    1 栈运算受限制线性表 (√)
    2 栈空情况作出栈操作否产生溢 (√)
    3 栈定序存储线性结构 (×)
    4 栈特点进先出 (√)
    5 空栈元素0栈 (×)
    6 C(C++)语言中设序栈长度MAXLENtopMAXLEN时表示栈满 (×)
    7 链栈序栈相特点通常会出现栈满情况 (√)
    8 栈输入序列:ABCD输出序列:CABD (×)
    9 递定义循环定义 (×)
    10 十进制数转换二进制数栈典型应 (√)
    二填空题
    1 栈结构中允许插入删端称 栈顶
    2 序栈中栈顶指针top1时表示 栈空
    3 n元素栈中进栈操作时间复杂度 O(1)
    4 栈中出栈操作时间复杂度 O(1)
    5 已知表达式求缀表达式 栈 典型应
    6 链栈中栈顶指针等NULL表示 栈空
    7 栈顶指针top链栈插入新结点*p时应执行p>nexttoptopp操作
    8 序栈S存储数组S>data[0…MAXLEN1]中进栈操作时执行语句:S>top++(S>top+1)
    S>data[S>top]x
    9 链栈LS指栈顶元素指针LS>next
    10 栈删元素时首先取出 栈顶元素 然移动栈顶指针
    11 链栈操作链表头部进行没必设置 头 结点
    12 已知序栈SS进栈操作前首先判断 栈否满
    13 已知序栈SS出栈操作前首先判断 栈否空
    14 空间充足 链 栈定义栈满运算
    15 链栈LS空条件 LS>nextNULL
    16 链栈LS栈顶元素链表 首 元素
    17 栈元素类型 相
    18 进栈次序ABCDE执行3次出栈操作栈顶元素 B
    19 A+BCD*E缀表达式 ABC+DE*
    20 4元素ABCD序进S栈执行两次Pop(Sx)运算x值 C
    三选择题
    1 插入删操作端进行线性表称( C )
    A.队列 B.循环队列 C.栈 D.循环栈
    2 设编号12344辆列车序进入栈结构站台列出站序( D)
    A.1234 B.1243 C.1324 D.1423
    3 果链表作栈存储结构出栈操作时( B )
    A.必须判栈否满 B.必须判栈否空 C.必须判栈元素类型 D.栈做判
    4 元素ABCD次进栈栈顶元素( D )
    A.A B.B C.C D.D
    5 序栈存储空间实现( B )存储元素
    A.链表 B.数组 C.循环链表 D.变量
    6 C(C++)语言中序栈旦声明占空间( A )
    A.已固定 B.固定 C.改变 D.动态变化
    7 带头结点链栈LS示意图栈顶元素( A )
    LS

    H A B C D ∧

    A.A B.B C.C D.D
    8 链栈序栈相较明显优点( B )
    A 插入操作更加方便 B通常会出现栈满情况 C会出现栈空情况 D删操作更加方便
    9 栈顶指针top链栈中删结点时x保存删结点应执行列(d )命令
    A.xtoptop>next Btoptop>nextxtop>data
    Cxtop>data Dxtop>datatoptop>next
    10 栈顶指针HS链栈中S指针指结点入栈应执行列( B )命令
    AHS>nextS BS>nextHS>nextHS>nextS
    CS>nextHS>nextHSS DS>nextHSHS>next
    11 4元素ABCD序进S栈执行两次Pop(Sx)运算栈顶元素值( B )
    A.A B.B C.C D.D
    12 元素ABCD次进栈栈底元素( A )
    A.A B.B C.C D.D
    13 列栈运算执行ReadTop(s)值( A )
    InitStack(s)Push(sa) Push(sb)Pob(s)
    A a Bb C1 D0
    14 列栈运算x值( B )
    InitStack(s)(初始化栈) Push(sa) Push(sb) ReadTop(s) Pob(sx)
    A a Bb C1 D0
    15 列栈运算x值( B )
    InitStack(s)(初始化栈) Push(sa) Pob(sx) Push(sb) Pob(sx)
    Aa Bb C1 D0
    16 列栈运算SEmpty(s)值( C )
    InitStack(s)(初始化栈) Push(sa) Push(sb) Pob(sx) Pob(sx)
    Aa Bb C1 D0
    17 序栈中输入元素时( B )
    A.先存入元素移动栈顶指针 B.先移动栈顶指针存入元素
    C.谁先谁关紧 D.时进行
    18 初始化空间5序栈SS>top值( B )
    A.0 B.1 C.改变 D.动态变化
    19 设入栈次序ABCDE栈输出序列( C )
    A.EDCBA B.DECBA C.DCEAB D.ABCDE
    20 设序栈S元素ABCDEF次进栈果6元素出栈序BDCFEA栈容量少应( A )
    A.3 B.4 C.5 D.6
    第4章 队列
    判断题
    1 队列限制两端进行操作线性表 (√)
    2 判断序队列空标准头指针尾指针指结点 (√)
    3 链队列做出队操作时会改变front指针值 (×)
    4 循环队列中尾指针rear头指针front元素数rearfront (√)
    5 单循环链表中头指针hp指结点尾结点条件ph (×)
    6 链队列定范围会出现队满情况 (√)
    7 循环链队列中溢出现象 (×)
    8 栈队列序存储线性结构 (×)
    9 队列中允许删端称队尾 (×)
    10 序队循环队关队满队空判断条件样 (×)
    二填空题
    1 队列中存取数应遵循原 先进先出
    2 队列 限定表端进行插入运算表端进行删运算线性表
    3 队列中允许插入端称 队尾
    4 队列中允许删端称 队首(队头)
    5 队列进行出队操作时首先判断队列否 空
    6 序队列进行入队操作时首先判断队列否 满
    7 序队列初始化初始化frontrear 1
    8 解决序队列假溢出方法采 循环队列
    9 循环队列队指针front队尾指针rear队空条件 front rear
    10 链队列LQ空时LQ>front>next NULL
    11 设长度n链队列单循环表表示设头指针入队操作时间复杂度 O(n)
    12 设长度n链队列单循环表表示设尾指针入队操作时间复杂度 O(1)
    13 链队列中队首指针队尾指针值相表示该队列 空
    14 设循环队列头指针front指队首元素尾指针rear指队尾元素空闲元素队列空间MAXLEN队满标志 front (rear+1)MAXLEN
    15 链队列中队首指针front队尾指针rear判断队列结点条件front rearfront
    16 循环队列中插入元素时首先判断 队尾指针 然指针指位置写入新数
    17 读队首元素操作 改变影响队列元素数
    18 设循环队列容量40(序号0~39)现系列入队出队运算front11rear19循环队列中 8 元素
    19 队列Q列运算:InitQueue(Q)(初始化队列)InQueue(Qa)InQueue(Qb)OutQueue(Qx)ReadFront(Qx)QEmpty(Q)值 8
    20 队列QInitQueue(Q)(初始化队列)InQueue(Qa)InQueue(Qb)ReadFront(Qx)x值 a
    三选择题
    1 队列限定(D)进行操作线性表
    A.中间者 B队首 C队尾 D端点
    2 队列中元素数(B)
    A.变 B变 C意 D0
    3 队列元素类型(A)
    A必须致 B致 C致 D限制
    4 队列(C)线性表结构
    A加限制 B推广 C加限制 D非
    5 利n数组序存储队列时该队列元素标(B)
    An2 Bn1 Cn Dn+1
    6 循环队列旦说明占空间(A)
    A已固定 B变动 C固定 D动态变化
    7 循环队列占空间(A)
    A必须连续 B必连续 C连续 D连续
    8 存放循环队列元素数组data10元素data数组标范围(B)
    A0~10 B0~9 C1~9 D1~10
    9 进队序列ABCD出队序列(C)
    ABCDA BACBD CABCD DCBDA
    10 4元素ABCD序连续进队Q队尾元素(D)
    A.A B.B C.C D.D
    11 4元素ABCD序连续进队Q执行次QutQueue(Q)操作队头元素(B)
    AA BB CC DD
    12 4元素ABCD序连续进队Q执行4次QutQueue(Q)操作执行QEmpty(Q)值(B)
    A0 B1 C2 D3
    13 队列Q列运算x值(B)InitQueue(Q)(初始化队列)InQueue(Qa)InQueue(Qb)OutQueue(Qx)ReadFront(Qx)
    Aa Bb C0 D1
    14 循环队列SQ队满条件(B)
    ASQ>rear SQ>front B(SQ>rear+1)MAXLEN SQ>front
    CSQ>rear 0 DSQ>front 0
    15 设链栈中结点结构:data数域next指针域top栈顶指针想链栈栈顶插入指针s指结点应执行列(A)操作
    As>nexttop>nexttop>nexts Btop>nexts
    Cs>nexttoptop>next Ds>nexttoptops
    16 带头结点链队LQ示意图链队列队头元素(A)


    LQ>front

    H A B C D ∧

    LQ>rear
    A.A B.B C.C D.D
    17 带头结点链队列LQ示意图指链队列队头指针(C)
    LQ>front

    H A B C D ∧

    LQ>rear
    ALQ>front BLQ>rear CLQ>front>next DLQ>rear>next
    18 带头结点链队列LQ示意图进行进队运算时指针LQ>frnot(A)
    LQ>front

    H A B C D ∧

    LQ>rear
    A始终改变 B时改变 C进队时改变 D出队时改变
    19队列Q列运算执行QEmpty(Q)值(C)
    InitQueue(Q)(初始化队列)InQueue(Qa)InQueue(Qb)OutQueue(Qx)ReadQueue(Qx)
    Aa Bb C0 D1
    206数组实现循环队列前frontrear值分30队列中删元素加入两元素frontrear值分(B)
    A51 B42 C24 D15
    第5章 串
    判断题
    1 串n字母限序列 (×)
    2 串数元素字符 (√)
    3 串长度指串中字符数 (×)
    4 果两串含相字符说明相等 (×)
    5 果串中字母均串中出现说明前者者子串 (×)
    6 串堆分配存储种动态存储结构 (√)
    7 DTDATA子串 (×)
    8 串中意字符组成子序列称该串子串 (×)
    9 子串定位运算称模式匹配 (√)
    10 链串中提高存储密度应该增结点 (√)
    二填空题
    1 零字符组成限序列称 字符串(串)
    2 字符串存储方式分序存储链接存储 堆分配存储
    3 串序存储结构简称 序串
    4 串序存储非紧凑格式缺点 空间利率低
    5 串序存储紧凑格式缺点串字符处理 效率低
    6 串链接存储优点插入删方便缺点 空间利率
    7 CC++语言中字符 \0 表示串值终结
    8 空格串长度等 空格数
    9 空串空格串中长度0 空格串
    10 两串相等指两串长度相等应位置 字符相
    11 设SMy MusicLenStr(s) 8
    12 两字符串分S1Today isS230 July2005ConcatStr(S1S2)结果 Today is 30 July2005
    13 求子串函数SubStr(Today is 30 July2005134)结果 July
    14 串运算中EqualStr(aaaaab)返回值 <0
    15 串运算中EqualStr(aaaaaa)返回值 0
    16 子串定位运算中匹配串称目标串子串称 模式
    17 模式匹配成功起始位置称 效位移
    18 设SabccdcdccbaaTcdcc第 6 次匹配成功
    19 设Scmydocumenttext1docTmydont字符定位位置 0
    20 n串长度m子串长度n>>m模式匹配算法坏情况时间复杂度 (nm+1)*m
    三选择题
    1 串种特殊线性表特殊体现(B)
    A.序存储 B.数元素字符C.链接存储 D.数元素字符
    2 某串长度常数采(B)存储方式节省空间
    A.链式 B.序 C.堆结构 D.法确定
    3 述正确(C)
    A.空串空格串相B.telTeleptone子串
    C.空串零字符串 D.空串长度等1
    4 述正确(B)
    A.空串空格串相B.tonTeleptone子串
    C.空格串空格串 D.空串长度等1
    5 断正确(A)
    A.全部空格组成串空格串 B.BEUIJINGBEI JING子串
    C.something6 设两串S1S2EqualStr(S1S2)运算称作(D)
    A.串连接 B.模式匹配 C.求子串 D.串较
    7 串模式匹配指(D)
    A.判断两串否相等 B.两串较
    C.找某字符串中第次出现位置D.找某子串串中第次出现第字符位置
    8 字符串ABCDEFG采链式存储假设字符占1字节指针占2字节该字符串存储密度(D)
    A.20 B.40 C.50 D.333
    9 字符串ABCDEFG采链式存储假设指针占2字节希存储密度50结点应存储(A)字符
    A2 B3 C4 D5
    10 设串S1IAMS2A SDUDENTConcatStr(S1S2)(B)
    A.I AM BI AM A SDUDENT CIAMASDUDENT DA SDUDENT
    11 设SLenStr(S)(A)
    A0 B1 C2 D3
    12 设目标串TAABBCCDDE模式PABCDE该模式匹配效位移(A)
    A0 B1 C2 D3
    13 设目标串TAABBCCDDEEFF模式PCCD该模式匹配效位移(D)
    A2 B3 C4 D5
    14 设目标串Taabaababaabaa模式Pabab模式匹配算法外层循环进行(D)次
    A1 B9 C4 D5
    15 模式匹配算法坏情况时间复杂(D)
    AO(m) BO(n) CO(m+n) DO(m×n)
    16 Smorning执行求子串函数SubSur(S22)结果(B)
    A mo B or C in D ng
    17 S1goodS2morning执行串连接函数ConcatStr(S1S2)结果(A)
    A goodmorning B good morning C GOODMORNING D GOODMORNING
    18 S1good S2morning执行函数SubSur(S24LenStr(S1))结果(B)
    Agood Bning Cgo Dmorn
    19 设串S1ABCDEFGS2PQRSTConcatStr(SubStr(S12LenStr(S2))SubStr(S1LenStr(S2)2))结果串(D)
    A BCDEF BBCDEFG CBCPQRST DBCDEFEF
    20 串SSOFTWARE子串数目(C)
    A.35 B36 C37 D38
    第6章 维数组广义表
    判断题
    1 n维维数视n1维数组元素组成线性结构 (√)
    2 稀疏矩阵中非零元素数远矩阵元素总数 (√)
    3 三角矩阵角线(包括角线元素)均常数C (×)
    4 数组元素干数项组成 (√)
    5 数组三元组表存储稀疏矩阵压缩存储 (√)
    6 矩阵进行压缩存储 (×)
    7 广义表线性表推广广义表线性表 (×)
    8 广义表LS(a0a1……an1)an1表尾 (×)
    9 广义表((ab)ab)表头表尾相等 (√)
    10 广义表表尾总广义表 (√)
    二填空题
    1 维数组序存储方式行优先序存储 优先序存储 两种
    2 维数组中数元素存放址直接通址计算公式算出维数组
    种 机 存取结构
    3 n维数组中元素 n 直接前驱
    4 输出二维数组A[n][m]中元素值时间复杂度 n(n*m)
    8 0 0 0 0 0
    0 11 0 0 0 0
    0 0 0 6 0 0
    0 3 0 0 7 0
    0 5 0 0 0 0
    0 0 0 0 9 0

    图619 稀疏矩阵A
    5 数组元素a[0…2][0…3]实际址2000元素长度4LOC[12] 2024
    6 稀疏矩阵三元组 3 列
    7 稀疏矩阵三元组中第1列存储数组中非零元素 行数
    8 n阶称矩果存储三角元素需 n(n1)2 存储单元
    9 稀疏矩阵A图619示非零元素存三元组表中三元组(415)列优先序存储三元组表第 4 项
    10 稀疏疏矩阵压缩存储方法通常三元组表 十字链表 两种
    11 非空广义表表尾必定广义表(子表)
    12 tail(head((ab)(cd) b
    13 设广义表((abc))c分离出运算 head(tail(tail(head(L))))
    14 广义表现出((ab)cd)表尾 (cd)
    15 n阶三角矩阵角线方常数需 n(n1)2+1 存储单元
    16 稀疏矩阵中n非零元素三元组 n 行
    17 广义表LS(a(b)((c(d))))长度 3
    18 广义表LS(a(b)((c(d))))深度 4
    19 广义表LS(()L)L深度 ∞
    20 广义表LS(a(b)((c(d))))表尾 ((b)((c(d))))
    三选择题
    1 m维数组中(D)恰m直接前驱m直接界继
    A开始结点 B总终端结点 C边界结点 D部结点
    2 述矩阵进行压缩存储失机存取功(D)
    A称矩阵 B三角矩阵 C三角矩阵 D稀疏矩阵
    3 行优先序存储三元组表中述陈述错误(D)
    A行非零元素列号递增次序存储B 列非零元素行号递增次序存储
    C三元组表中三元组行号递增 D 三元组表中三元组列号递增
    4 稀疏矩阵进行压缩存储(B)
    A降低运算时间B节约存储空间C便矩阵运算D便输入输出
    5 数组A[0‥m] [0‥n]列优先序存储aij址(A)
    ALOC(a00)+[j×m+i] B LOC(a00)+[j×n+i] C LOC(a00)+[(j1)×n+i1] D LOC(a00)+[(j1)×m+i1]
    6 列矩阵(B)
    A. 称矩阵 B.三角矩阵 C.稀疏矩阵 D.带状矩阵
    1 0 0 0
    2 3 0 0
    4 5 6 0
    7 8 9 10
    7 稀疏矩阵三元组表示法中三元组表示(D)
    A.矩阵非零元素值 B.矩阵中数元素行号列号
    C.矩阵中数元素行号列号值 D.矩阵中非零数元素行号列号值
    8 已知二维数组A[6][10]数组元素占4存储单元行优先序存储存放数组元素a[3][5]存储址1000a[0][0]存储址(B)
    A.872 B.860 C.868 D.864
    9 广义表线性表推广间区(A)
    A.否子表 B.肥否原子项 C.否空 D.表长度
    10 列广义表属线性表(B)
    AE(aE) BE(abc) CE(a(bc)) DE(aL)L()
    11 广义表((ab)cd)表尾(D)
    A.a B.d C.(ab) D.(cd)
    12 广义表A((x(ab))(x(ab)y))运算head(head(tail(A)))(A)
    A. x B.(ab) C.(x(ab)) D.A
    13 tail(head((ab)c(cd)))结果(B)
    A. b B.(b) C.(ab) D.(d)
    14 广义表满足head(L)tail(L)L形式(B)
    A.空表 B.L(a1…an)a1(a2…an)
    C.L(a1…an)(a1a2…an) D.((a1)( a1))
    15 数组(B)线性表结构
    A非 B推广 C加限制 D加限制
    16 数组A[0:10:10:1](D)元素
    A4 B5 C6 D8
    17 广义表((ab)cd)表头(C)
    A a Bd C(ab) D(cd)
    18 广义表A(a)表尾(C)
    A a B(()) C空表 D(a)
    19 (C)稀疏矩阵压缩存储方法
    A维数组 B二维数组 C三元数组 D广义表
    20 设广义表D(abcd)深度(D)
    A2 B3 C4 D∞
    第7章 树二叉树
    判断题
    1 树结构中结点直接前驱 (√)
    2 完全二叉树定满二叉树 (×)
    3 中序线索二叉树中右线索空定指双亲 (×)
    4 棵二叉树中序遍历序列结点必定该二叉树前序遍历结点(√)
    5 二叉树前序遍历中意结点均处子女结点前面 (√)
    6 二叉树前序遍历序列中序遍历序列推导出序遍历序列 (√)
    7 完全二叉树中结点没左孩子必然叶子结点 (√)
    8 哈夫曼编码中两字符出现频率相编码相种情况应该做特殊处理(×)
    9 含两棵树森林转换二叉树根结点定右孩子 (×)
    10 具n叶子结点哈夫曼树2n1结点 (√)
    二填空题
    1 树中结点拥子树数称该结点 度
    2 度零结点称 叶(叶子终端) 结点
    3 树中结点层次称树 深度(高度)
    4 二叉树说第i层 2i1 结点
    5 深度h二叉树 2h1 结点
    6 棵二叉树前序序列 中序 序列唯确定棵二叉树
    7 20结点完全二叉树编号10结点父结点编号 5
    8 哈夫曼树带权路径长度 二叉树
    9 二叉树序 中序 遍历序列唯确定棵二叉树
    10 某二叉树中序遍历序列:DEBAC序遍历序列:EBCAD前序遍历序列 DABEC
    11 设棵二叉树结点先序遍历序历:ABDECFGH中序遍历序历:DEBAFCHG二叉树中叶结点: EFH
    12 已知完全二叉树第8层8结点叶结点数 68
    13 树转换二叉树时根结点 右子树
    14 采二叉链表存储n结点二叉树 2n 指针域
    15 采二叉链表存储n结点二叉树空指针 n+1
    16 前序ABC序CBA二叉树 4 种
    17 三结点组成 2 种形态树
    18 棵完全二叉树层次编号意编号i结点左孩子结点编号: 2*i
    19 定图736示二叉树前序遍历序列: ABEFHCG
    20 定图737示二叉树层次遍历序列: ABCEFGH

    A A

    B C B C

    E F G 图736 二叉树1 E F G 图737 二叉树2

    HD HD
    三选择题
    1 树适合表示(D)
    A序数元素 B序数元素 C元素间联系数 D元素间分支层次关系
    2 前序ABC二叉树(D)种
    A2 B3 C4 D5
    3 根二叉树定义具3结点二叉树(C)种树型
    A3 B4 C5 D6
    4 棵具五层满二叉树中结点点数(B)
    A16 B31 C32 D33
    5 具64结点完全二叉树深度(C)
    A5 B6 C7 D8
    6 棵二叉树叶结点前序中序序遍历序列中相次序(A)
    A发生改变 B发生改变 C确定 D
    7 AB棵二叉树两结点中序遍历时AB前条件(C)
    AAB右方 BAB祖先 CAB左方 DAB子孙
    8 列4棵树中(B)完全二叉树
    A. A B A C A D A

    B C B C B C B C

    D E HD G D E F D E D

    9 图738示二叉树序遍历序列(D)
    AABCDEFGHI A
    BABDHIECFG 图738二叉树3
    CHDIBEAFCG B C
    DHIDEBFGCA
    D E F G
    H I
    10 图739示二叉树中序序序列(A)
    A. DBEHAFCG BDBHEAFCG CABDEHCFG DABCDEFGH
    A

    B C

    D E F G 图739二叉树4

    H
    11 某二叉树序遍历序列:DABEC中序遍历序列:DEBAC前序遍历序列(D)
    AACBED BDECAB CDEABC DCEDBA
    12 具n(n>1)结点完全二叉树中结点i(2i>n)左孩子结点(D)
    A2i B2i+1 C2i1 D存
    13 棵树转换二叉树棵二叉树形态(A)
    A唯 B种 C种根结点没左孩子 D种根结点没右孩子
    14 棵100结点完全二叉树左右次结点编号根结点编号1编号45结点左孩子编号(B)
    A46 B47 C90 D91
    15 棵100结点完全二叉树左右次结点编号根结点编号1编号49结点右孩子编号(B)
    A98 B99 C50 D100
    16 二叉树某种序线索化结点均指前驱继线索种说法(B)
    A正确 B错误 C确定 D
    17 列陈述正确(D)
    A二叉树度2序树 B二叉树中结点孩子时左右分
    C二叉树必度2结点 D二叉树中两棵子树左右子树分
    18 5权值{32451}构造哈夫曼树带权路径长度(B)
    A32 B33 C34 D15
    19 树结构中结点B4兄弟AB父亲结点A度(C)
    A3 B4 C5 D6
    20 二叉树叶结点数度2结点数(C)
    A关 B相等 C D少
    第8章 图
    判断题
    1 图没边没顶点 (√)
    2 图中(v1v2)(v2v1)两条边 (×)
    3 邻接表图存储 (×)
    4 图邻接矩阵表示唯 (√)
    5 邻接矩阵法存储图时占存储空间图中顶点数关图边数关(×)
    6 图进行广度优先遍历 (×)
    7 图顶点v1起点进行深度优先遍历遍历序列唯唯确定该图 (√)
    8 存储图邻接矩阵称存储邻接矩阵三角(三角)部分 (√)
    9 邻接表法存储图时占存储空间图中边数关结点数关 (×)
    10 图中顶占出发进行次深度优先遍历访问图中顶点该图定连通 (√)
    二填空题
    1 图常存储方式邻接矩阵 邻接表 等
    2 图遍历: 深度优先搜 广度优先搜等方法
    3 n条边图邻接矩阵中1数 2n
    4 图边称 弧
    5 图邻接矩阵表示法表示 顶点 间相邻关系矩阵
    6 图G邻接矩阵存储第i行元素等顶点i 出度
    7 n顶占e条边图采邻接矩阵存储空间复杂度: On2
    8 n顶占e条边图采邻接表存储空间复杂度: O(n+e)
    9 设稀疏图GG采 邻接表 存储较节省空间
    10 设稠密图GG采 邻接矩阵 存储较节省空间
    11 图逆邻接表存储结构适 图
    12 n顶点完全图 n(n1)2 条边
    13 图邻接矩阵表表示适求顶点 出度
    14 图邻接矩阵表示中第i列非0元素数顶点vi 入度
    15 具n顶点图生成树仅 n1 条边
    16 n顶点e条弧图邻接表表示中需 n+e 结点
    17 图中某顶点出发访遍历图中余顶点顶点仅访问次称程图 遍历
    18 图邻接矩阵定 称 矩阵
    19 连通网生成树该图生成树中 权 生成树
    20 求稠密图G生成树 Prim 算法求解
    三选择题
    1 图中顶点度数等图边数(C)倍
    A12 B1 C2 D4
    2 图中顶点入度等顶点出度(B)倍
    A12 B1 C2 D4
    3 具n顶点图边数(B)
    An Bn(n1) Cn(n1)2 D2n
    4 具n顶点图中连通全部顶点少需(C)条边
    An Bn+1 Cn1 Dn2
    5 8结点完全图( C)条边
    A14 B28 C56 D112
    6 深度优先遍历类似二叉树(A)
    A先序遍历 B中序遍历 C序遍历 D层次遍历
    7 广度优先遍历类似二叉树(D)
    A先序遍历 B中序遍历 C序遍历 D层次遍历
    8 连通图生成树(A)
    A棵 B棵棵 C定棵 D存
    9 图顶点v度关联该顶点B)数目
    A顶点 B边 C序号 D标
    10 n顶点图邻接矩阵(B)数组存储
    A维 Bn行n列 C意行n列 Dn行意列
    11 具n顶点e条边图采邻接表表示表头量(C)
    An1 Bn+1 Cn Dn+e
    12 图表示法中表示形式唯(A)
    A邻接矩阵表示法 B邻接表表示法 C逆邻接表表示法 D邻接表逆邻接表表示法
    13 具n顶点e条边图中顶点度数等(C)
    A n Be C2n D2e
    v1 1 a a

    v2 v3 2 3 b c b c
    e e
    v4 v5 4 5 d f d f

    图823度3结点 图824(15)题 图825顶点a出发 图826优先遍历
    14 图823中度3结点(B)
    AV1 BV2 CV3 DV4
    15 图824(A)
    A连通图 B强连通图 C生成树 D环图
    16 图825示顶点a出发深度优先进行遍历种顶点序列(D)
    Aabecdf Bacfebd Caebcfd Daedfcb
    17 图826示顶点a出发广度优先进行遍历种顶点序列(A)
    Aabecdf Babecfd Caebcfd Daedfcb
    18 生成树构造(A)算法
    APrim算法 B卡尔算法 C哈夫曼算法 D迪杰斯特拉算法
    19 面关图存储结构叙述中正确(A)
    A邻接矩阵存储图占空间图中顶点数关边数关
    B邻接矩阵存储图占空间图中边数关顶点数关
    C邻接存储图占空间图中顶点数关边数关
    D邻接存储图占空间图中边数关顶点数关
    20 连通分量(C)极连通子图
    A 树 B图 C图 D图
    第9章 查找
    判断题
    1 二分查找法求查表关键字值必须序 (√)
    2 序表言采二分查找总采序查找法速度快 (×)
    3 二叉排序树中根结点值孩子结点值 (×)
    4 散列存储法基思想关键字值决定数存储址 (√)
    5 哈希表种关键字转换存储址存储方法 (√)
    6 选择哈希函数避免突发生 (×)
    7 序序表序链表均采二分查找提高查找速度 (×)
    8 采分块查找实现线性表希查找速度适应动态变化需 (√)
    9 哈希查找效率取决哈希表构造时选取哈希函数处理突方法 (√)
    10 二叉排序树删结点时必移动结点该结点父结点相应指针域置空 (×)
    二填空题
    1 序查找法表中元素 意 存放
    2 分块查找方法中首先查找 索引 然查找相应块
    3 序查找二分查找分块查找属 静态 查找
    4 静态 查找表含元素数查找阶段固定变
    5 长度n线性表进行序查找时间复杂度 O(n)
    6 长度n线性表采二分查找时间复杂度 O(log2n)
    7 理想情况散列表中查找元素时间复杂度: O(1)
    8 关键字序列(710121828364592)中二分查找法查找关键字92较 4 次找
    9 设100元素二分查找法查找时较次数 7 次
    10 二叉排序树进行查找方法查值根结点键值进行较根结点值继续
    左 子树中查找
    11 二叉排序树种 动态 查找表
    12 哈希表 散列 存储方式构造存储结构
    13 哈希法种存储方法种 查找 方法
    14 散列表查找效率取决散列表造表时选取散列函数处理 突 方法
    15 设散列函数H键值k1k2k1≠k2 H(k2 )H(k2)称种现象 突
    16 处理突两类方法开放定址法 拉链法(链址法)
    17 散列表(散列) 查找法均查找长度元素数n关
    18 哈希函数H(key) keyP中P般应取 质数
    19 查找程中插入元素删元素操作称 动态 查找
    20 结点左右子树深度差绝值 1 二叉树称衡二叉树
    三选择题
    1 查找表(A)查找结构
    A集合 B图 C树 D文件
    2 序查找法适合存储结构(B)线性表
    A散列存储 B序存储链接存储C压缩存储 D索引存储
    3 表长n链表中进行线性查找均查找长度(B )
    AASLn BASL(n+1)2 CASL+1 DASL≈log2n
    4 线性表进行二分查找时求线性表必须(D)
    A序方式存储 B链接方式存储结点关键字序排序
    C链接方式存储 D序方式存储结点关键字序排序
    5 衡量查找算法效率标准(B)
    A元素数 B均查找长度 C需存储量 D算法难易难度
    6 果求线性表较快查找适应动态变化求采(A)查找方法
    A分块 B序 C二分 D散列
    7 链表适(A)查找
    A序 B二分 C机 D序二分
    8 序表{139123241456275778295100}二分查找值82结点时(C)次较查找成功
    A2 B3 C4 D5
    9 二分查找序表{4610122030507088100}查找表中元素58次表中(B)较查找结果失败
    A30887050 B20703050 C2050 D308850
    10 14元素序A[1‥14]作二分查找查找元素A[4]时较元素次(C)
    AA[1]A[2]A[3]A[4] BA[1]A[14]A[7]A[4]
    CA[7]A[3]A[5]A[4] DA[7]A[5]A[3]A[4]
    11 长度12序表二分查找法进行查找表元素等概率情况查找成功需均较次数(B)
    A3512 B3712 C3912 D4312
    12 采分块查找时线性表625元素查找生元素等概率相等假设采序查找确定结点块时块分(C)结点佳
    A.6 B.10 C.25 D.625
    13 列(C)利查找表中数元素关系进行查找方法
    A.衡二叉树 B.序表查找 C.散列查找 D.二叉排序树查找
    14 设哈希表长m14哈希函数H(key)key11表中已4结点:addr(15)4 addr(38)5
    addr(61)6 addr(84)7余址空二次探测散列处理突关键字49结点址(D)
    A.8 B.3 C.5 D.9
    15 包含n元素散列表进行查找均查找长度(D)
    A.O(n2) B.O(log2n) C.O(n) D.直接赖n
    16 突指(C)
    A.两元素具相序号 B.两元素键值
    C.键值应相存储址 D.两元素键值相
    17 查找程中做增加删修改查找称(A)
    A.静态查找 B.创造 C.动态查找 D.处查找
    18 已知8元素{3476451826549265}次插入结点方法生成棵二叉排序树两层结点总数(B)
    A.1 B.2 C.3 D.4
    19 生成图917示二叉排序树关键字序列(A)
    A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5
    4

    2 5

    1 3 图917二叉树
    20 动态查找包括(B)查找
    A序表 B二叉排序树 C序表 D索引序表
    第10章 排序
    判断题
    1 果某种排序算法稳定该排序方法没实价值 (×)
    2 希尔排序稳定排序 (√)
    3 泡排序稳定排序 (×)
    4 n记录进行快速排序需均时间O(nlog2n) (√)
    5 堆排序需时间排序记录数关 (×)
    6 排序元素数时交换元素位置占较时间影响时间复杂度素 ( √ )
    7 快速排序情况排序方法速度快 (×)
    8 快速排序说初始序列正序反序坏情况 (√)
    9 采排序实现外排序 (√)
    10 采希尔排序时原始关键字排列杂乱序效率高 (√)
    二填空题
    1 数排序算法两基操作: 较 移动
    2 评价排序算法优劣标准 时间复杂度 算法需附加空间
    3 根处理数计算机中存储设备排序分 排序 外排序
    4 外排序指排序程中数部分存计算机 外存 中
    5 n关键字进行泡排序较次数 n1 次
    6 坏情况第i趟直接插入排序中进行 i1 次关键字较
    7 n关键字进行泡排序时间复杂度 O(n2 )
    8 快速排序坏情况时间复杂度 O(n2)
    9 n记录集合进行排序需均时间 O(nlog2n)
    10 n记录集合进行排序需附加空间 O(n)
    11 原始数接序选 快速排序
    12 排序前关键字值相等记录排序相位置保持 变 排序方法称稳定排序方法
    13 插入排序选择排序中初始数基正序选 插入排序较
    14 增量1时该趟希尔排序 直接插入 排序基致
    15 第趟排序序列中键值记录交换排序算法 泡 排序
    16 次面文件记录插入前面序子文件中排序方法称直接插入 排序
    17 插入排序选择排序排序中稳定排序: 选择 排序
    18 组记录(543896231572604593)进行直接插入排序时第7记录60插入序表时寻找插入位置需较 3 次
    19 两序列分:L1{2557483792861233}
    L2 {2537331248578692}
    泡排序法L1 L2进行排序交换次数较少序列: L2
    20 组记录(543596211272604480)进行直接选择排序时第4次选择交换未排序记录 5472609680
    三选择题
    1 排序根(A )重新安排元素序
    A关键字 B数组 C元素件 D结点
    2 评价排序算法坏标准(D)
    A执行时间 B辅助空间 C算法身复杂度 D执行时间需辅助空间
    3 直接插入排序方法( B )排序方法
    A稳定 B稳定 C外部 D选择
    4 直接插入排序方法求排序数(B)存储
    A必须链表 B必须序 C序链表 D意
    5 排序方法中序序列中选择关键字记录序区(初始空)第记录交换排序方法称(D)
    A希尔排序 B排序 C插入排序 D选择排序
    6 次排序数划分左右两区间中左区间中元素值基准元素值右区间中元素值基准元素值种排序方法称(C )
    A泡排序 B堆排序 C快速排序 D排序
    7 快速排序( C)情况易发挥长处
    A排序数中含相关键字B排序数已基序
    C排序数完全序 D排序数中值值相差悬殊
    8 述种排序方法中求存量( D )
    A插入排序 B选择排序 C快速排序 D排序
    9 直接插入排序方法第( B )元素开始插入前边适位置排序方法
    A1 B2 C3 Dn
    10 堆形状棵( C )
    A二叉排序树 B满二叉树 C完全二叉树 D衡二叉树
    11 排序指排序整程中全部数计算机( A )中完成排序
    A存 B外存 C存外存 D寄存器
    12 快速排序方法(A )排序方法
    A稳定 B稳定 C外部 D选择
    13 列排序方法中关键字较次数记录初始排列次序关( A)
    A选择排序 B希尔排序 C插入排序 D泡排序
    14 述种排序方法中均时间复杂度(A)
    A希尔排序 B插入排序 C泡排序 D选择排序
    15 n记录表作快速排序坏情况算法时间复杂度(B)
    AO(n) BO(n2) CO(nlog2n) DO(n3)
    16 泡排序方法n数进行排序第趟排序需较(C )次
    A1 B2 Cn1 Dn
    17 n排序码进行泡(递增)排序列(B )情况较次数
    A排列 B排列C元素序 D元素基序
    18 直接插入排序法面4序列进行排序元素较次数少(B)
    A9432409080462169 B2132464080699094
    C3240214669949080 D9069804621329440
    19 组记录排序码(2548163579822340)中含4长度2序表排序方法该序列进行趟结果( A)
    A16 25 35 48 23 40 79 82 B16 25 35 48 79 82 23 40
    C16 25 48 35 79 82 23 40 D16 25 35 48 79 23 40 82
    20 数序列关键字(467956384084)采快速排序第数基准第次划分结果(C )
    A(384046567984) B(403846795684)
    C(403846567984) D(403846795684)
    第十章文件
    1.文件:性质相记录集合放外存
    关键字项:唯标识记录数项数项组合(学号)
    文件操作:检索维护
    文件存贮结构:序索引散列链
    文件组织方式:序文件索引文件散列文件关键字文件

    2.序文件:记录进入文件先序存放逻辑序物理序致文件
    序文件更新方法:
    优点:
    3.索引文件:文件外外建立张表:逻辑记录物理记录应关系表文件起构成文件索引文件
    4.索引序文件:索引表关键字序文件关键字序
    索引非序文件索引表关键字序文件关键字序
    ISAM文件:专磁盘存取设计文件组织方式静态索引结构级索引柱面索引磁道索引文件组成
    VSAM文件:虚拟存贮存取方法B+树动态索引结构文件三部分组成:索引集序集数集
    5.散列文件:散列存贮方式组织文件直接存取文件
    桶:
    6.关键字文件:包含次关键字索引文件
    重表文件:索引方法链接方法相结合种组织方式
    倒排文件:重表次关键字索引结构

    三应题(题5题题6分30分)
    26已知广义表图形表示图示
    (1) 写出该广义表L
    (2) 分写出该广义表深度长度
    L((e) () (a(bcd)) (bcd))
    深度3
    长度4


    27已知二叉树先序序列中序序列分ABDEHCFIDBHEACIF
    (1) 画出该二叉树二叉链表存储表示
    (2) 写出该二叉树序序列DHEBIFCA
    A
    B C
    D E F
    H I
    28已知图邻接表图示
    (1) 写出顶点A出发该图进行广度优先搜索遍历顶点序列:ABDCE
    (2) 画出该图逆邻接表

    29次读入定整数序列{716482096185}完成列操作:
    1)构造棵二叉排序树计算等概率情况该二叉排序树均查找长度ASL
    2)变更序列中元素排列构造出均查找长度达二叉排序树写出满足述求序列中第元素
    7
    4 16
    6 8 20
    5 9 18
    ASL19*(1+2*2+3*3+3*4)269
    {975481861620}
    9
    7 18
    5 8 16 20
    4 6
    ASL19*(1+2*2+4*3+2*4)259

    26森林转换应二叉树图示写出原森林中第三棵树
    前序序列序序列

    G
    H I
    J
    前序序列:GHI J
    序序列:HJIG
    27图邻接表类型定义示:
    #define MaxVertexNum 50
    typedef struct node
    { int adjvex
    struct node *next
    }EdgeNode
    typedef struct
    {
    VertexType vertex
    EdgeNode *firstedge
    }VertexNode
    typedef VertexNode AdjList[MaxVertexNum]
    typedef struct {
    AdjList adjlist
    int n e
    }ALGraph
    便删插入图顶点操作邻接表表头量定义链式结构两种定义存储表示实例图示请写出重新定义类型说明
    题27图




    typedef struct link
    { VertexType vertex
    EdgeNode *firstedge
    link *down
    }

    typedef struct node
    { struct node *next
    struct link *next1
    }EdgeNode
    struct Link * ALGraph

    28某类物品编号写英文字母2位数字(09)组成形E32运基数排序列物品编号序列进行字典序排序写出趟(分配收集)结果
    E13A37F43B32B47E12F37B12
    第趟:B32E12B12E13F43A37B37F37
    第二趟:E12B12E13B32A37F37F43B47
    第三趟:A37B12B32B47E12E13F37F43

    29(1)画出表长13序序表进行二分查找判定树
    A[6]28
    A[3] 16 A[10] 67
    A[1] 12 A[4] 21 A[8]43 A[12]84
    A[2] 14 A[5] 24 A[7] 35 A[9] 52 A[11] 71 A[13] 99

    (2)已知关键字序列(12141621242835435267718499)写出该序列中二分查找37时需进行较次数5

    29.栈输入端元素输入序123456进栈程中退栈退栈时否排成序列325641154623写出进栈退栈程简述理(push(x)表示x进栈pop(x)表示x退栈)
    push(1)push(2)push(3)pop(3) pop(2) push(4)push(5)
    POP(5)push(6)pop(6) pop(4) pop(1)
    30.已知棵二叉树中根遍历序列CBEDFAGH根遍历序列CEFDBHGA画出该二叉树
    A
    B G
    C D H
    E F

    31.定表(15118201413)试元素表中序次插入棵初始时空二叉排序树画出插入完成二叉排序树判断该二叉排序树否衡二叉排序树非衡二叉排序树调整衡二叉排序树
    15
    11 20
    8 14
    13
    调整方法:
    根结点衡:根左子树高>右子树高+1:根中序序列81113141520中根前点14移根
    14
    11 15
    8 13 20

    根左子树高<右子树高+1:根中序序列中根点移根

    33.泡排序法(快速排序)数序列(49386597761342749)进行排序写出排序程说明泡排序否稳定排序
    泡排序法稳定
    49386597761342749
    49659776134384927
    65977613449493827
    977613465494938 27
    9713476 65494938 27
    13497 76 65494938 27


    快速排序稳定
    49386597761342749
    49382749761349765
    27384949657697134
    27384949657697134




    29已知3阶B树图示
    (1)画出关键字6插入B树
    (2)画出(1)树中插入关键字2B树
    2

    5

    6



    2

    1

    3


    2

    8

    9



    2

    3

    6



    2

    1

    2


    1

    5




    2

    8

    9



    32.题32图示图(1)写出邻接矩阵(2)写出三种顶点A起点深度优先搜索顶点序列
    a0 1 1 0 0 0 0 1
    b1 0 0 1 1 00 0
    c0 0 0 0 0 1 0 0
    d0 1 0 1 0 0 0 0
    e0 1 0 0 0 1 0 0
    f 0 0 1 0 0 0 0 0
    g0 0 0 1 1 0 0 0
    h10 0 0 0 0 0 0

    图619 稀疏矩阵A

    ACFBEGDH
    ABDGEHCF
    AHBEGDCF

    28假设通信电文字符集 {abc d e f g h}
    字符电文中出现频度分:7262281310311试8字符设计哈夫曼编码求:
    (1)画出构造哈夫曼树(求树中左孩子结点权值右孩子结点权值)
    (2)左分支0右分支1规分写出字符应编码
    100
    46 54
    21 25 26b 28d
    10f 11h 12 13e
    5 7a
    2c 3g
    A0101 b10 c01000 d00 e011 f000 g01001 h001

    四算法阅读题(题4题题5分20分)
    四算法阅读题(题4题题5分20分)
    30假设带头结点单链表表示线性表阅读列算法f30回答问题
    (1) 设线性表( a1 a2 a3 a4 a5 a6 a7 ) 写出执行算法f30线性表
    (2) 简述算法f30功
    void f30(LinkList L)
    {
    L带头结点单链表头指针
    LinkList pq
    P L
    while (p &&p–>next)
    {q p–>next q指第点
    p–>next q–>next p指第二点删第点
    p q–>next p指第二点
    free(q)回收q
    }
    }
    (1) (a2 a3 a4 a5 a6 a7 )
    (2) 删链表第点(头结点)
    31算法f31功助栈结构实现整数10进制8进制转换阅读算法回答问题:
    (1) 画出n十进制1348时算法执行程中栈动态变化情况
    (2) 说明算法中while循环完成操作
    void f31(int n) n非负十进制整数
    {
    int e
    SeqStack S
    InitStack(& S)
    do{
    Push(& Sn8)
    n n8
    }while (n)
    while ( StackEmpty(& S)){e Pop(& S)printf (〞ld〞e)}
    }
    (1)405 2





    (2)栈空时出栈输出n化8进制数序列2504

    32已知二叉链表作二叉树存储结构阅读算法f32回答问题:
    (1) 设二叉树T图示写出执行f32(T)返回值
    (2) 简述算法f32功
    int f32(BinTree T)
    {
    int m n
    if( T)
    return 0
    else
    { m f32(T–>lchild)
    n f 32(T–>rchild)
    if(m>n)return m +1
    else return n+1
    }
    }
    (1)
    (2)
    33设图邻接表定义
    typedef struct{
    VertexNode adjlist[Max VertexNum]
    int ne 图前顶点数弧数
    } ALGraph 邻接表类型
    vertex
    firstedge
    中顶点表结点VertexNode结构:

    adjvex
    next
    边表结点EdegNode结构:

    阅读列算法f33回答问题:
    (1)已知图G邻接表图示
    写出算法f33输出结果
    (2)简述算法f33功
    void dfs (ALGraph *Gint v)
    {
    EdgeNode * p
    visited[v]TRUE
    printf(〞c〞G–>adjlist[v]·vertex)
    for(p G–>adjlist[v])·firstedge p pp–>next)
    if( visited[p–>adjvex])
    dfs (G p–>adjvex)
    }
    void f33(ALGraph *G)
    {
    int vw
    for(v0 v n v ++) {
    for(w0wn w++)
    visited[w]FALSE
    printf(〞d 〞v)
    dfs(Gv)
    printf(〞﹨n〞)
    }
    }

    30假设带头结点单链表表示线性表单链表类型定义:

    typedef int DataType
    typedef struct node {
    DataType data
    struct node * next
    } LinkNode * LinkList
    阅读列算法回答问题:
    (1)已知初始链表图示画出执行f30(head)链表

    题30图
    (2)简述算法f30功
    void f30( LinkList head)
    { LinkList pr s
    if (head > next) {
    r head > next
    p r>next
    r > next NULL
    while (p) {
    s p
    p p>next
    if ( s > data 2 0) {
    s > next head > next
    head > next s
    } else {
    s > next r > next
    r>next s
    r s
    } } } }
    (1)
    2
    8
    5
    7

    (2)原链中偶数置前奇数置
    31假设二叉链表表示二叉树类型定义:
    typedef struct node {
    DataType data
    struct node * lchild * rchild 左右孩子指针
    } * BinTree

    阅读列算法回答问题:
    (1)已知T根指针二叉树图示
    写出执行f31(T)返回值
    (2)简述算法f31功
    int f31 ( BinTree T)
    { int d
    if ( T) return 0
    d f31 ( T > lchild) + f31 ( T > rchild)
    if (T > lchild && T > rchild)
    return d + 1
    else
    return d
    (1)
    (2)
    32设图邻接表定义:
    typedef struct {
    VertexNode adjlist[ MaxVertexNum ]
    int ne //图前顶点数弧数
    }ALGraph //邻接表类型
    中顶点表结点VertexNode
    边表结点EdgeNode结构:
    阅读列算法回答问题:
    (1)已知某图存储图示邻接
    表G中写出执行f32(&G)输出
    (2)简述算法f32功
    int visited[ MaxNum ]
    void DFS(ALGraph * G int i) {
    EdgeNode * p
    visited [ i ] TRUE
    if (G > adjlist[ i] firstedge NULL)
    printf( c G > adjlist[ i] vertex)
    else {
    p G > adjlist[ i] firstedge
    while (p NULL) {
    if ( visited[p > adjvex] )
    DFS( G p > adjvex)
    p p>next
    }
    }
    }
    void f32 ( ALGraph * G) {
    int i
    for (i 0 i < G>n i ++)
    visited [ i ] FALSE
    for (i 0 i < G>n i++)
    if ( visited[i] ) DFS(G i)
    }
    (1)
    (2)
    33列算法f33功记录序列进行双泡排序算法基思想先前通交换关键字记录移动端然前通交换关键字记录移动前端反复进行直整序列关键字递增序止请空缺处填入合适容成完整算法

    #define MAXLEN 100
    typedef int KeyType
    typedef struct {
    KeyType key
    InfoType otherinfo
    } NodeType
    typedef NodeType SqList[ MAXLEN ]
    void f33 ( SqList R int n)
    { int ijk
    NodeType t
    i 0
    j nl
    while (i < j) {
    for ( kik if (R[k]key > R[k +l]key) {
    t R[k]
    R[k] R[k +1]
    R[k +1] t
    }
    j
    for (k j k > i k )
    if (R[k1]key > R[k ]key ) {
    t R[k]
    R[k] R[k1]
    R[k1] t
    }

    文档香网(httpswwwxiangdangnet)户传

    《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
    该内容是文档的文本内容,更好的格式请下载文档

    下载文档到电脑,查找使用更方便

    文档的实际排版效果,会与网站的显示效果略有不同!!

    需要 2 香币 [ 分享文档获得香币 ]

    下载文档

    相关文档

    数据结构练习题(含答案)

    数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的① 、数据信息在计算机中的② 以及一组相关的运算等的课程。 ...

    3年前   
    1474    0

    数据结构试题及答案多套

    数据结构试卷(一) 1数据结构试卷(二) 4数据结构试卷(三) 6数据结构试卷(四) 8数据结构试卷(五) 11数据结构试卷(六) 14数据结构试卷(七) 16数据结构试卷(八) 18数据结构...

    3年前   
    871    0

    十套数据结构试题及答案

    数据结构试卷(一) 1数据结构试卷(二) 4数据结构试卷(三) 6数据结构试卷(四) 8数据结构试卷(五) 11数据结构试卷(六) 14数据结构试卷(七) 16数据结构试卷(八) 18数据结构...

    3年前   
    640    0

    数据结构习题集附答案

    数据结构习题集附答案第一章 绪 论一、选择题1.组成数据的基本单位是( )A.数据项 B.数据类型 C.数据元素 D.数据变量2.数据结构是研究数据的( )以及它们之间的相互关系。A.理...

    3年前   
    842    0

    数据结构实习报告

    数据结构实习报告  一、需求分析1、  程序所实现的功能;2、  程序的输入,包含输入的数据格式和说明;3、  程序的输出,程序输出的形式;4、  测试数据,如果程序输入的数据量比较大,需要给...

    8年前   
    1028    0

    《简爱》练习题和答案

    简•爱是个孤女,出生于一个穷牧师家庭。父母由于染上伤寒,在一个月之中相继去世。幼小的简寄养在舅父母家里。舅父里德先生去世后,简过了10年受尽歧视和虐待的生活。一次,由于反抗表哥的殴打,简被关进了...

    1年前   
    438    0

    数据结构考试题(浙江科技学院)无答案

    题序一二三四五六七总分得分命题:得分一、单项选择题。在题后括号内,填上正确答案代号。(本大题共15小题,每小题2分,总计30分)。1.数据结构是研究数据的( )以及它们之间的相互关系。(A...

    5个月前   
    146    0

    数据结构(C语言版)(第2版)课后习题答案

    数据结构(C语言版)(第2版) 课后习题答案 目 录第1章 绪论 1第2章 线性表 5第3章 栈和队列 13第4章 串、数组和广义表 26第5章 树和二叉树 33第6章 图 43第...

    2年前   
    633    0

    数据结构考试题库含答案

    数据结构习题集含答案目录目录 1选择题 2第一章绪论 2第二章 线性表 4第三章 栈和队列 5第四章 串 6第五章 数组和广义表 7第六章 树和二叉树 7第七章 图 9第八章 查找 11第九章...

    3年前   
    1019    0

    数据结构试验迷宫问题

    数据结构试验——迷宫问题(一)基本问题1.问题描述这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入,让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行,迷宫唯...

    2年前   
    510    0

    数据结构实验报告

    实验报告课程:数据结构 班级:网络工程 学号: 姓名: 实验1 链表的插入和删除一、实验目的 1、...

    1年前   
    321    0

    数据结构实践报告

     数据结构实践报告学 号: 姓 名: 班 级: ...

    1年前   
    567    0

    《皇帝的新装》练习题及答案(2套)

    一、基础部分1.下边加粗字的注音有误的一组是(  )A.头衔(xián) 钦差(qīn) 陛下(bì)B.称职(chènɡ) 爵位(jué) 温和(hé)C.附和(hè) 炫耀(xuàn)...

    2年前   
    595    0

    《昆虫记》练习题及答案

    1、《昆虫记》是一部(世界昆虫史诗);3、这部书将(昆虫)世界化作供人获得(知识)、(;5、蟋蟀它之所以如此名声在外,主要是因为它的(住;6、(蝉)不靠别人生活;7、蝉怎样喝水?(用它突出的嘴-...

    3年前   
    1919    0

    《论语》六则练习题(含答案)

    第一部分:1.给下列加点字注音:(6分)论语(  ) 不亦说乎(  ) 不愠(  ) 三省(  ) 罔(  ) 殆(  ) 2.填空:《论语》是记录 的一部书。是   家经典著作之一。孔子...

    4年前   
    1300    0

    《傅雷家书》练习题及答案

    1、《傅雷家书》主要讲的是( )。 如何教育孩子 2、《傅雷家书》曾荣获“( )” 全国首届优秀青年读物 3、傅雷是我国著名文学翻译家、文艺评论家。他翻...

    1年前   
    555    0

    过去完成时练习题及答案

    练习一一 . 用动词的适当形式填空1. We _____________ (paint) the house before we ______________ (move) in.2. Tha...

    4年前   
    1078    0

    保密法练习题及答案

    保密法练习题及答案

    5年前   
    31685    2

    2.6体积单位练习题及答案

    2. 联系实际,填写适当的单位。(1)一缸水有4(  )。(2)一杯橘子汁有500(  )。(3)一桶色拉油有2.1(  )。(4)一个集装箱的体积是120(  )。

    2年前   
    459    0

    离散数学练习题含部分答案

    2016注意事项:1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外,把大纲中指定的例题及书后习题认真做一做。检验一...

    1年前   
    641    0

    文档贡献者

    文***享

    贡献于2020-10-31

    下载需要 2 香币 [香币充值 ]
    亲,您也可以通过 分享原创文档 来获得香币奖励!
    下载文档

    该用户的其他文档